O(VN)_一维数组完全背包

基于一维的01背包

首先想想为什么01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态fi是由状态f[i-1] [v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个*绝无已经选入第i件物品的 子结果 *f[i-1] [v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果fi]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

01背包于完全背包的区别就在于：01背包的dp[i] [j] 需要dp[i - 1] [j - v[i]]这个子结果，即在选第i - 1个物品时且剩余的容量恰好够v[i]的子结果，因为在选第i - 1 个时绝对不可能选了第i 个，这样就保证的一件物品只能选一次；

而完全背包第 I 件物品可选无限件，所以在考虑“加选一件第 i 种物品“时，需要考虑是：可能已经选入第 i 种物品的子结果dp[i] [j - v[i]]

参考代码:

#include<iostream>
using namespace std;
const int M = 10000;
int m, n;
int dp[M], w[M], c[M];
int main(){
	cin>>m>>n;
	for(int i = 0; i < n; i++){
		cin>>w[i]>>c[i];
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= m; j++){
			if(j >= w[i]){
				dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
			}
		}
	}
	cout<<"max="<<dp[m];
	return 0;
}