01背包问题

1.

二维表示

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 int n,m; //个数和背包容量
 6 int v[N],w[N]; //每个物品的体积和价值
 7 int f[N][N]; //表示状态
 8 
 9 int main()
10 {
11     cin >> n >> m;
12     
13     for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; //读入所有的物品
14     
15     // f[0][0 ~ m] = 0; //0个没有意义，且全局变量已经初始化
16     
17     //f[i][j] 表示从1~i的数，总价值不超过j的集合
18     for (int i = 1; i <= n; i ++ ) //枚举个数
19       for (int j = 0; j <= m; j ++ ) //枚举体积
20       {
21           f[i][j] = f[i - 1][j];
22           if(j >= v[i]) f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]); //判断是否为空集
23       }
24       cout << f[n][m];
25       
26       return 0;
27 }