01、多重、完全背包板子

【01背包】

给你n种不同的物品，每个物品有自己的重量w[i]，和价值v[i]，如果每个物品只能拿一次，给你容量为m的背包，怎样才能取得最大价值？

状态转移方程：dp[j]=MAX{dp[j],dp[j-w[i]]+v[i]}

基本操作：

1
2
3

for(i=0;i<n;i++)
       for(j=m;j>=w[i];j--)//01是从最大到当前
             dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

dp[j]用来记录当容量为j时的可行取法的最大价值。

【多重背包】

给你n种不同的物品，每个物品有自己的重量w[i]，和价值v[i]，如果每个物品最多只能拿c[i]个，给你容量为m的背包，怎样才能取得最大价值？

状态转移方程：dp[j]=MAX{dp[j],dp[j-kw[i]]+kv[i]};
但是一般会T，所有要用二进制或者拆分01完全优化

二进制优化

for(i=0;i<n;i++)
	{
		for(k=1;k<<1<c[i];k<<=1)
		{
			for(j=V;j>=k*v[i];j--)
			{
				dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
			}
		}
		m=c[i]-k+1;
		for(j=V;j>=m*v[i];j--)
		{
			dp[j]=max(dp[j],dp[j-m*v[i]]+m*w[i]);
		}
	}

coins那道题的板子，01拆分后二进制优化了

#include<iostream> 
#include<algorithm>
#include<string.h>
#define INF 0x3f3f3f3f
using namespace std;
//手表价格 
int m; 
//单位货币的价值
int val[1005];
//单位货币的数量
int vol[1005];
int dp[100005];
void Zero(int cost){
	for(int i=m;i>=cost;i--)
		dp[i]=max(dp[i],dp[i-cost]+cost);
}
//val*vol>>m，硬币可以无限使用，可以使用完全背包 
void Com(int cost){
	for(int i=cost;i<=m;i++)
		dp[i]=max(dp[i],dp[i-cost]+cost);
}
//拆分vol,价格系数k*vol组成新硬币 
void mul(int val,int vol){
	if(val*vol>=m)
		Com(val);
	else{
		int k=1;
		while(k<=vol){
			Zero(k*val);
			vol-=k;
			k*=2;
		}
		Zero(vol*val);
	}
}
int main(){
	//货币的种类 
	int n;
	while(cin>>n>>m,(n||m)){
		for(int i=1;i<=n;i++)
			cin>>val[i];
		for(int i=1;i<=n;i++)
			cin>>vol[i];
		memset(dp,0,sizeof(dp));
		for(int i=0;i<=m;i++)
			dp[i]=-INF;
		dp[0]=0;
		for(int i=1;i<=n;i++)
			mul(val[i],vol[i]);
		int ans=0;
		for(int i=1;i<=m;i++)
			if(dp[i]>0)
				ans++;
		cout<<ans<<endl;
	}
	return 0;
}

【完全背包】

给你n种不同的物品，每个物品有自己的重量w[i]，和价值v[i]，一个物品可以拿多次，给你容量为m的背包，怎样才能取得最大价值？

分析：类似于01背包问题，在01背包问题中，物品要么取，要么不取，而在完全背包中，物品可以取0件、取1件、取2件…直到背包放不下位置。因此，可以直接在01背包的递推式中扩展得到。

状态转移方程：dp[j]=MAX{dp[j],dp[j-w[i]]+v[i]}

基本操作：

1
2
3

for(i=1;i<=n;i++)
      for(j=w[i];j<=m;j++)  //注意此处与01背包不同，01为倒序
             dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

一个简单有效的优化

完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。