简单的背包问题

描述 小冯有个存储重量为m的空间存储袋，现在有n件物品，每件物品的重量为w，价值为v。 问小冯最多能装的最大价值为多少？

输入 第一行输入两个数m、n，（1<=n,m<=1000）n表示物品数量，m表示存储袋的最大重量;

接下来的n行，每行输出w,v,(1<=w,v <= 100)分别表示物品的重量，物品的价值; 输出 输出小冯能装的物品最大价值; 样例输入 70 3 71 100 69 1 1 2 样例输出 3

题解 利用动态空间规划 可以建立一个二维数组存储物品价值，行为物品个数，列为重量 比较和比这个物品重量小的物品的价值的和，和上一个物品价值的值哪个大 否则返回上一个物品的价值

个数/重量	0	1	2	3
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	0	0
4	0	0	0	0

放入第一个物品重量为1，价值为2

个数/重量	0	1	2	3
0	0	0	0	0
1	0	2	2	2
2	0	0	0	0
3	0	0	0	0
4	0	0	0	0

放入第二个物品重量为2，价值为4

个数/重量	0	1	2	3
0	0	0	0	0
1	0	2	2	2
2	0	2	4	6
3	0	0	0	0
4	0	0	0	0

代码实例

#include<iostream>
#include<cstdlib>
using namespace std;
int m, n, i, j;
int w[1000], c[1000], f[1000][1000];
int main()
{
	cin >> m >> n;//m代表背包最大能装的重量，n代表物品的数量
	for (i = 1; i <= n; i++) {
		cin >> w[i] >> c[i];//输入每个物品的重量和价值
	}
	//i控制物品，j控制重量
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (j >= w[i]) {
				f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]);
			}
			else{
				f[i][j] = f[i - 1][j];
			}
		}
	}
	cout << f[n][m] << endl;

	return 0;
}

vector版：

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
int n, w, i, j;
int main()
{
	cin >> w >> n;
	//定义容器行为几号物品，列为重量
	vector<vector<int>>f(n + 1, vector<int>(w+1,0));
	//定义重量与价值的容器
	vector<int>weight(n +1);
	vector<int>price(n + 1);
	//输入
	for ( i = 1; i <= n; i++) {
		cin >> weight[i] >> price[i];
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= w; j++) {
			if (j >= weight[i]) {
				f[i][j] = max(f[i - 1][j - weight[i]] + price[i], f[i - 1][j]);//比较和比这个物品重量小的物品的价值的和，和上一个物品价值的值哪个大
			}
			else {
				f[i][j] = f[i - 1][j];//否则返回上一个物品的价值
			}
		}
	}
	cout << f[n][w] << "\n";
	return 0;
}