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.
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)ththings.(dp[i−1][j])
Then choose the best situation.
The code would looks like this:
1 | for (int i = 0; i < n; i ++) { |
We can’t optimize the time complexity because we need to traverse n things and Vpackage volume. However, we can optimize its space complexity.
1 | for (int i = 0; i < n; i ++) { |
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.