C++求解01背包问题

描述

你是一个探险家，有一天，你在某个神秘的洞穴中发现N件珠宝，每件珠宝上写着其重量wi和价值vi。由于你发现得比较晚，这个地方随时会出现塌陷等事故，这事你就得考虑把一部分珠宝放入你的随身背包中带走，以便不虚此行。但是，由于你个子吃紧，最多可以带走的珠宝总重量不超过W，那你将如何挑选呢？

输入格式

第一行：N M，表示N件珠宝，你的承重能力W

接下来是N行，每行输入wi vi，表示第i件珠宝的单重和单价

输出格式

一行，表示你能带走珠宝的最佳方案所能达到的价值

示例

输入

【3件珠宝，10总承重】

【珠宝重量[9,5,5]】 【珠宝价值[9,5,5]】

3 10
9 9
5 5
3 5

输出

【应该挑第2件和第3件珠宝带走，总重量8小于自身承重，总价值10】

10

代码

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main() {
	int N,W;
	cin>>N>>W;

	vector<int> w(N+1,0);
	vector<int> v(N+1,0);
	for(int i=1; i<=N; i++) {
		cin>>w[i]>>v[i];
	}

	vector<vector<int> > res(N+1,vector<int>(W+1,0));
	for(int i=1; i<=N; i++) {
		for(int j=0; j<=W; j++) {
			if(j<w[i]) {
				res[i][j]=res[i-1][j];
			} else {
				res[i][j]=max(res[i-1][j],res[i-1][j-w[i]]+v[i]);
			}
		}
	}

	cout<<res[N][W]<<endl;
	return 0;
}

运行结果

3 10
9 9
5 5
3 5
10

--------------------------------
Process exited after 6.262 seconds with return value 0
请按任意键继续. . .

解析

?把二维数组res当做求解空间 ，第一维度表示已经对前几个珠宝做完决定?

?第二维度表示已经使用背包载量，使用动态规划算法进行求解。

对于第i件珠宝，如果剩余载量不足，则跟这件珠宝不在没有区别，于是总价不变

但当剩余载量足够，则需要比较载入与否的总价，择优选取。

刚遇到的小伙伴可能难以理解，不要急躁，多看几遍就理解了。

?由于举例的数字比较小，大家可以搞个二维表格表示res来帮助理解。