[DP 01 backpack]

01 knapsack

• Why call 01 knapsack ？

  Because each item can only be used once , Or don't have to .

• State transition equation ：
  $$f[i][j]=Max(f[i-1][j],f[i-1][j-v[i]]+w[i])$$

• State escape equation after optimization ：
  $$f[j]=Max(f[j],f[j-v[i]]+w[i])$$

• The results of the analysis ：f[N][v]

Detailed analysis

• This problem can be regarded as the problem of finding the extreme value of a finite set .

• emm, Look at my messy handwritten notes .

---

Related topics

Yes NN Items and a capacity are VV The backpack . Each item can only be used once .

The first ii The volume of the item is vivi, The value is wiwi.

Find out which items to pack in your backpack , The total volume of these items can not exceed the capacity of the backpack , And the total value is the greatest .
Output maximum value .

Input format

The first line has two integers ,N,VN,V, Space off , They are the number of items and the volume of the backpack .

Next there is NN That's ok , Two integers per line vi,wivi,wi, Space off , Separate indication control ii The volume and value of items .

Output format

Output an integer , Represents the greatest value .

Data range

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

sample input

4 5
1 2
2 4
3 4
4 5

sample output ：

8

---

Solution code

• Violent version

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
int v[N], w[N];

int main() {
    
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
    
        cin >> v[i] >> w[i];
    }

    for (int i = 1; i <= n; i ++) {
    
        for (int j = 0; j <= m; j ++) {
    
            f[i][j] = f[i - 1][j];
            // printf("i = %d, j = %d, f[%d][%d] = %d, f[%d][%d] = %d\n", i, j, i, j, f[i][j], i - 1, j, f[i - 1][j]);
            if (j >= v[i]) {
    
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    }

    int res = 0;
    for (int i = 0; i <= m; i ++) {
    
        res = max(res, f[n][i]);
    }

    cout << res << endl;

    return 0;
}

• Optimized version

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
// int f[N][N];
int f[N];
int v[N], w[N];

int main() {
    
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
    
        cin >> v[i] >> w[i];
    }

    for (int i = 1; i <= n; i ++) {
    
        for (int j = m; j >= v[i]; j --) {
    
            //  It doesn't include  i  Items 
            f[j] = f[j];
            if (j >= v[i]) {
    
                //  Including  i  Items 
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        }
    }
    cout << f[m] << endl;

    return 0;
}

---