背包九讲之一：01背包问题：一个物品只允许选一次

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 /*
 5 f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少
 6 result = max{f[n][0-v]}
 7 1.不选第i个物品，f[i][j]=f[i-1][j];
 8 2.选第i个物品，f[i][j]=f[i-1][j-v[i]]+w[i]（v[i]是体积，w[i]是价值）
 9 f[0][0]=0;
10 */
11 const int array_size = 1001;
12 int f[array_size][array_size], v[array_size], w[array_size], N, V;
13 int main() {
14     cin >> N >> V;
15     for (int i = 1; i <= N; ++i)
16         cin >> v[i] >> w[i];
17     for (int i = 1; i <= N; ++i)
18         for (int j = 0; j <= V; ++j) {
19             f[i][j] = f[i - 1][j];
20             if(j>=v[i])
21                 f[i][j] = max(f[i-1][j], f[i - 1][j - v[i]] + w[i]);
22         }
23     /*
24     不能直接使用
25     for (int i = 1; i <= N; ++i)
26         for (int j = v[i]; j <= V; ++j)
27             f[i][j] = max(f[i-1][j], f[i - 1][j - v[i]] + w[i]);
28     因为漏掉了j<v[i]时，一定满足f[i][j]=f[i-1][j]的情况。
29     例如i=1,j=2，v[1]=1,w[1]=3时,2>=v[1],f[1][2]=3
30     下轮i=2,j=2，v[2]=3,w[2]=4时,2<v[2],f[2][2]=0，出错。应当f[2][2]=f[1][2]=3
31     */
32     cout << f[N][V]; //表示的是物品个数<=N，体积<=V的最大价值
33 }

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int array_size = 1001;
 5 int f[array_size], v[array_size], w[array_size], N, V;
 6 int main() {
 7     cin >> N >> V;
 8     for (int i = 1; i <= N; ++i)
 9         cin >> v[i] >> w[i];
10     for (int i = 1; i <= N; ++i)
11         /*
12         1、此处若j正序，在第i轮（前i个物品）中，由于j-v[i]<j,先算的是f[j-v[i]],
13         再算f[j]。则f[j-v[i]]相当于上例中的f[i][j-v[i]]。
14         2、若j倒叙，在第i轮中，先算f[j],再算f[j-v[i]]。则f[j-v[i]]
15         相当于上例中的f[i-1][j-v[i]]。故使用倒叙。
16         */
17         for (int j = V; j >= v[i]; --j)
18             f[j] = max(f[j], f[j - v[i]] + w[i]);
19     /*
20     迭代过程中并未考虑上例红字部分的问题。因为第i轮中的f[j]
21     未重新赋值前天然就是第i-1轮中的f[j]
22     */
23     cout << f[V];//f[V]表示的是体积<=V的最大价值
24 }
25 /*
26 若是要求物品恰好装满背包时的最大价值，只需
27 初始化时将f[0]置0，f[1]-f[V]都置-INF就可以了。
28 确保所有状态都是由f[0]转移过来。
29 */