01 背包

物品只有拿或不拿

状态表示

集合：表示所有选法，是前 i 个物品中选，体积 ⇐ j 的所有选法

属性：max；min；数量

相当于 dp[i][j] 表示前 i 个物品中选，体积 ⇐ j 的所有选法的集合，就是说代表了这件事。然后这个值，为最大价值，具体的一个最大价值，这个集合中各种选法中的最大值

状态计算

就是集合划分，如何将现在的集合通过更小的集合表示出来

对于背包问题，经常这么划分：

• 不包含 i 这个物品的，恰好就是 dp[i-1][j]
• 包含 i 这个物品的，恰好就是 dp[i-1][j-vi] + vi

代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N][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++) {
			if(j >= v[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
			else dp[i][j] = dp[i-1][j];
		}
	}
	cout << dp[n][m] << endl;
}

这里我觉得判断 j 和 vi 的那一步还不是那么好想，如果直接说要背包容量足以装 vi 才行，但 j 不是总的背包容量吗？应该是剩余空间足够装 vi 才对

确实，所以建议先考虑因为要索引 j-v[i]，所以考虑成索引合法就行了。然后再来细究实际意义

实际上，这是在倒推，我说我 i 物品一定要放，最极端的不就是 i 价值很高，刚好塞满背包吗

另外，值得考虑的是边界情况，i-1 也不能超出呀，所以 i 从 1 开始，边界的 00 就是都是默认 0 正好也可以

优化为一维

一般可以优化都是因为这一层只用了前一层或前两层。这里就是只用了前一层

注意到，else 那里，新一层和前一层持平，说明去掉第一维之后，不动就是更新了

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--) {  // attention
			dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
		}
	}
	cout << dp[m] << endl;
}

然后 j 是从小到大增加的，也就是 dp 是从前往后更新的，而每次更新要用到 j 之前的元素，可是那个已经被更新了，所以倒过来循环，更新的时候前面还没被更新