## Question

There are n things, each thing has a volume $v[i]$, and a value $c[i]$. There is package with volume $Vpackage$. Choose some or all of the things to put into package, we want the total value of package is as big as possible. So you should calculate the biggest value.

## Recurrence Equation

We use $dp[i][j]$ to represents the total value of a j volume package with previous i things.

For each thing, there is two status: put it in to the package, or not put it in the package.

The recurrence equation is : $dp[i][j] = max(dp[i-1][j], dp[i - 1][j - v[i]] + c[i])$.

This is easy to understand.

If we put i-th thing in the package, the total value would be the value of previous (i-1)th things with package volume $j-v[i]$ add the value of i-th thing. ($dp[i - 1][j - v[i]] + c[i]$)

If we don’t put, the total value of previous i-th things would be the total value of previous (i-1)th things.($dp[i-1][j]$)

Then choose the best situation.

## Two-dimensional array

The code would looks like this:

## One-dimensional array

We can’t optimize the time complexity because we need to traverse n things and Vpackage volume. However, we can optimize its space complexity.

Why we reverse the second for loop? This is the hardest part for me.

As we know, the current $dp[i][j1]$ is got based on the $dp[i - 1][j1]$ and $dp[i - 1][j1 - v[i]]$.

If we use forward loop, at $i-1$, we calculated a $dp[j1 - v[i]]$, and this $dp[j1 - v[i]]$ is equal to $dp[i - 1][j1 - v[i]]$. We will use this to calculate $dp[i][j1]$.

However, when we are at $i$, we may encounter $dp[i][j1 - v[i]]$, then we update the $dp[j1 - v[i]]$ value to the $dp[i][j1 - v[i]]$. So when we use it later, we get wrong. We need to use $dp[j1 - v[i]]$ as $dp[i - 1][j1 - v[i]]$ but $dp[j1 - v[i]]$ has been updated to $dp[i][j1 - v[i]]$.

So we need to reverse the loop.