[动态规划]01背包问题（省空间复杂度）

[动态规划]0/1背包问题（省空间复杂度）

0/1背包问题是动态规划中最为经典的题目。
有n个物品，已知各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
样例输入：
3 8
3 3
5 4
5 5
样例输出：
8

上一篇文章中用了二维数组，比较浪费空间复杂度，这里使用一维数组，思路与上一篇相同。（一维数组只保留最高价值）
由于用了一维数组，所以关键判别式应为
f[j] = max(f[j], f[j - w[i]] + c[i]);

代码如下：

#include 
using namespace std;
int w[1001],c[1001],f[1001];
int main(){
	int i,j,m,n;
	cin >> m >> n;
	for (i = 1; i <= n; i++){
		cin >> w[i] >> c[i];
	}
	for (i = 1; i <= n; i++){
		for (j = m; j >= 0; j--){
			if (j >= w[i]){
				f[j] = max(f[j], f[j - w[i]] + c[i]);
			}
		}
	}
	cout << f[m];
	return 0;
}