感谢太阳大佬的讲解
0-1背包是一个经典的DP问题（主要是OI考）
定义
有N件物品和一个容量为V 的背包。放入第i件物品耗费的背包容量是W[i]，得到的价值是C[i]。求将哪些物品装入背包可使价值总和最大，而每件物品只有一个，可以选择不放。
0-1背包是其他背包问题的基础
无优化版本
我们用一个数组 f[i][v]来表示这个虚拟的背包，表示前i件物品恰放入一个容量为v的背包可 以获得的最大价值。
对于每一种物品，我们可以选或者不选，不选的话呢一切状态不变，选的话呢，则背包的容量减去W[i]，背包里的物品价值加上C[i]。
于是我们可得到它的状态转移方程：
F[ⅈ][v]=max(F[ⅈ−1][v],F[ⅈ−1][v−W[ⅈ]]+C[ⅈ])
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生 出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包 中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化 为一个只和前i−1件物品相关的问题。如果不放第i件物品，那么问题就转化 为“前i−1件物品放入容量为v的背包中”，价值为F[i−1,v]；如果放第i件物 品，那么问题就转化为“前i−1件物品放入剩下的容量为v −Wi的背包中”， 此时能获得的最大价值就是F[i−1,v −Wi]再加上通过放入第i件物品获得的价 值Ci。——《背包九讲》
//code by extmool
#include <iostream>
#define V 500 //可以用 const int V=500 来代替
using namespace std;
int weight[20 + 1];
int value[20 + 1];
int f[20 + 1][V + 1];
int main() {
int n, m;
cout << "请输入物品个数:";
cin >> n;
cout << "请分别输入" << n << "个物品的重量和价值:" << endl;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
cout << "请输入背包容量:";
cin >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (weight[i] > j) {
f[i][j] = f[i - 1][j];
}
else {
f[i][j] = f[i - 1][j] > f[i - 1][j - weight[i]] + value[i] ? f[i - 1][j] : f[i - 1][j - weight[i]] + value[i];
}
}
}
cout << "背包能放的最大价值为:" << f[n][m] << endl; //输出最大价值
}空间优化（重点）
我们压缩一下数组，方程就变成了这样
F[v]=max(F[v],F[v - W[ⅈ]] + C[ⅈ])
但是第二重循环要逆序
为什么可以逆序？
因为我们如果正序循环修改了1个数的话，后面可能会用该数进行2次辨断，这样可能会多选几次。
懒得敲代码了
//code by extmool
#include <iostream>
#define V 500
using namespace std;
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];
int main() {
int n, m;
cout << "请输入物品个数:";
cin >> n;
cout << "请分别输入" << n << "个物品的重量和价值:" << endl;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
cout << "请输入背包容量:";
cin >> m;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (weight[i] <= j) {
f[j] = f[j] > f[j - weight[i]] + value[i] ? f[j] : f[j - weight[i]] + value[i];
}
}
}
cout << "背包能放的最大价值为:" << f[m] << endl;
}后记
时间仓促，如有ｂｕｇ请大佬指出，Ｔｈａｎｋｓ %%%
至于正序会怎么样？ 秒变完全背包
Comments NOTHING