完全背包(C语言)

完全背包
与01背包不同之处就在于
它的物品可以取用无数次
可以研究一下的它的状态转移方程
所以从图中的推导就可以看出
将01背包滚动数组的逆序更新转换为顺序更新就行
因为根据状态转移方程可以看出

用到的是第i行的数据，所以需要顺序更新滚动数组
代码如下

#include
int f[2000];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 0;i < n;i++){
		int v,w;
		scanf("%d%d",&v,&w);
		for(int j = 0;j <= m;j++)//顺序更新
			if(f[j] < f[j-v]+w&&j >= v)	f[j] = f[j-v]+w;//状态转移方程
	} 
	printf("%d",f[m]);
}