多重背包--zoj_2156

         首先介绍经典的三种背包问题，0-1背包，完全背包，多重背包。0-1背包是背包问题的最简形式，其他的很多背包问题都可以转化为0-1背包来解决，而0-1背包问题也有非常简单的解法，时间效率为O(V*N),空间消耗为O(V),这里不要小看空间消耗，在数据量很大时，大量的取地址操作也会占用不少的时间消耗。

        0-1背包问题可以这样描述：给出N个背包，每个背包的重量为c[i]，价值为v[i]，在N个背包中选取k个，每个最多选1次，使得总的重量小于V而，总的价值最大。

        用DP，以dp[i][j]表述更新第i个背包，总重量为j时的最大价值。显然可以有以下状态转移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);简单分析一下效率发现是O(V*N),空间消耗为O(V*N).

       那么如何简化空间消耗呢，运用了很巧妙的一个技巧,在遍历j时从大到小遍历即可用dp[j]表示新第i个背包，总重量为j时的最大价值。仔细想想WSM会这样呢？如果从小到大遍历

dp[j]是由dp[j]和dp[j-c[i]]+v[i]更新而来的，而此时的dp[j]已经是dp[i][j]了，但我们需要的是dp[i-1][j]。仔细想想就可以明白。

        完全背包问题可以这样描述：给出N个背包，每个背包的重量为c[i]，价值为v[i]，在N个背包中选取k个，每个次数不限，使得总的重量小于V而，总的价值最大。

       朴素的解法就是在0-1背包的基础上遍历k，分析一下效率为V*sum(V/c[i])

       也有拆分法效率为V*sum(log(V/c[i]))，具体见背包9讲

       这里要重点介绍O(V*N)法，很简单也很巧妙，就是0-1背包优化解法的正向更新，在遍历j时从小到大遍历即可用dp[j]表示新第i个背包，总重量为j时的最大价值。

       WSM会这样呢？仔细想想也很简单，在0-1背包的时候，我们希望更新dp[j]的时候dp[j]和dp[j-c[i]]+v[i]都是在i-1时更新的值，而在完全背包时，每个背包可以取无限次，因此我们在更新dp[j]的时候恰恰需要的是在i时的dp[j]和dp[j-c[i]]+v[i]。

       最后介绍多重背包：给出N个背包，每个背包的重量为c[i]，价值为v[i]，在N个背包中选取k个，每个次数为n[i]，使得总的重量小于V而，总的价值最大。

       显然也可以遍历k，效率是V*sum(n[i]),这里介绍一种拆分法V*sum(log(n[i])),

很简单，把每一个系数为n[i]的背包拆分为，系数为2^0,2^1,2^2...n[i]-2^k的背包，背包的重量和价值都乘上相对应的系数即可。拆分后用0-1背包解。

zoj_2156

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int,int> clist[200];
int p,c1,c2,c3,c4;
int total,mid;
int inf=-999999;
//int dp[200][10005];
int dp[10005];
//int path[200][10005];
int path[10005];
int cnt[10005];
int flag[200];
void init()
{
	total=0;
	int tmp=1;
	mid=c1;
	while(mid>tmp)
	{
		mid=mid-tmp;
		clist[++total]=make_pair(1*tmp,1*tmp);
		flag[total]=1;
		tmp*=2;
	}
	clist[++total]=make_pair(1*mid,1*mid);	
	flag[total]=1;
	mid=c2;
	tmp=1;
	while(mid>tmp)
	{
		mid=mid-tmp;
		clist[++total]=make_pair(5*tmp,1*tmp);
		flag[total]=2;
		tmp*=2;
	}
	clist[++total]=make_pair(5*mid,1*mid);
	flag[total]=2;
	mid=c3;
	tmp=1;
	while(mid>tmp)
	{
		mid=mid-tmp;
		clist[++total]=make_pair(10*tmp,1*tmp);
		flag[total]=3;
		tmp*=2;
	}
	clist[++total]=make_pair(10*mid,1*mid);
	flag[total]=3;
	mid=c4;
	tmp=1;
	while(mid>tmp)
	{
		mid=mid-tmp;
		clist[++total]=make_pair(25*tmp,1*tmp);
		flag[total]=4;
		tmp*=2;
	}
	clist[++total]=make_pair(25*mid,1*mid);
	flag[total]=4;
	return;
}
void solve()
{
	/*for(int i=0;i<=total;++i)
	for(int j=0;j<=p;++j)
	{
		dp[i][j]=inf;
	}*/
	for(int j=0;j<=p;++j)
	{
		dp[j]=-1;
		cnt[j]=0;
	}
	dp[0]=0;
	/*for(int i=1;i<=total;++i)
	{
		for(int j=0;j<=p;++j)
		{
			if(j-clist[i].first>=0)
			{
				if(dp[i][j]<dp[i-1][j-clist[i].first]+clist[i].second&&dp[i-1][j-clist[i].first]+clist[i].second>=0)
				{	
					path[i][j]=flag[i];
					dp[i][j]=dp[i-1][j-clist[i].first]+clist[i].second;
				}
				else
				{
					path[i][j]=0;
				}
				//dp[i][j]=max(dp[i][j],dp[i-1][j-clist[i].first]+clist[i].second);	
			}	
			if(dp[i][j]<dp[i-1][j]&&dp[i-1][j]>=0)
			{
				dp[i][j]=dp[i-1][j];
				path[i][j]=0;
			}
			//dp[i][j]=max(dp[i][j],dp[i-1][j]);
		}
	}*/
	for(int i=1;i<=total;++i)
	{
		for(int j=p;j>=clist[i].first;--j)
		{
			if(dp[j]<dp[j-clist[i].first]+clist[i].second&&dp[j-clist[i].first]!=-1)
			{
				path[j]=j-clist[i].first;
				cnt[j]=flag[i];
				dp[j]=dp[j-clist[i].first]+clist[i].second;
			}
		}

	}
}
int main()
{
	freopen("e:\\zoj\\zoj_2156.txt","r",stdin);
	while(scanf("%d %d %d %d %d",&p,&c1,&c2,&c3,&c4)!=EOF)
	{
		if(p==0&&c1==0&&c2==0&&c3==0&&c4==0)
			break;
		init();
		solve();
		if(dp[p]<0)
			puts("Charlie cannot buy coffee.");
		/*if(dp[total][p]<0)
			puts("Charlie cannot buy coffee.");
			*/
		else
		{	
			//printf("%d\n",dp[total][p]);
			int c,n,d,q;
			c=n=d=q=0;
			int tmp=p;
			/*for(int i=total;i>=1;--i)
			{
				if(path[i][tmp]==0)
					continue;
				else
				{
					if(path[i][tmp]==1)
					{
						tmp-=clist[i].first;
						c+=clist[i].first/1;
					}
					if(path[i][tmp]==2)
					{
						tmp-=clist[i].first;
						n+=clist[i].first/5;
					}
					if(path[i][tmp]==3)
					{
						tmp-=clist[i].first;
						d+=clist[i].first/10;
					}
					if(path[i][tmp]==4)
					{
						tmp-=clist[i].first;
						q+=clist[i].first/25;
					}
				}	
			}
			*/
			while(tmp>0)
			{
				if(cnt[tmp]==0)
					continue;
				else
				{
					if(cnt[tmp]==1)
					{
						c+=(tmp-path[tmp])/1;
						tmp=path[tmp];
					}
					if(cnt[tmp]==2)
					{
						n+=(tmp-path[tmp])/5;
						tmp=path[tmp];
					}
					if(cnt[tmp]==3)
					{
						d+=(tmp-path[tmp])/10;
						tmp=path[tmp];
					}
					if(cnt[tmp]==4)
					{
						q+=(tmp-path[tmp])/25;
						tmp=path[tmp];
					}
				}
			}
			printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",c,n,d,q);
		}
	}		
}

 

背包模板,zoj_2156

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 10002
int num[4],v[4],ans[4];
int sum;
int dp[maxn];
int fa[maxn];
int cnt[maxn];
void pack1(int c,int k) //0 1 背包
{
    int v;
    for (v = sum;v>=c;v--)
    {
        if (dp[v] < dp[v-c]+k && dp[v-c]!=-1)
        {
            fa[v] = v - c;
            cnt[v] = k;
            dp[v] = dp[v-c]+k;
        }
    }
    return;
}
void pack2(int c) //完全背包
{
    int v;
    for (v = c;v<=sum;v++)
    {
        if (dp[v] < dp[v-c] + 1 && dp[v-c]!=-1)
        {
            fa[v] = v-c;
            cnt[v] = 1;
            dp[v] = dp[v-c] + 1;
        }
    }
    return;
}
void pack3(int c,int a) //多重背包
{
    if (c*a>=sum)
    {
        pack2(c);
        return;
    }
    int k = 1;
    while (a-k>0)
    {
        pack1(k*c,k);
        a = a - k;
        k*=2;
    }
    pack1(a*c,a);
    return;
}

int main()
{
    int i,tmp,k1;
    v[0] = 1;
    v[1] = 5;
    v[2] = 10;
    v[3] = 25;
	freopen("e:\\zoj\\zoj_2156.txt","r",stdin);
    while (scanf("%d%d%d%d%d",&sum,&num[0],&num[1],&num[2],&num[3]))
    {
        if (sum==0&&num[0]==0&&num[1]==0&&num[2]==0&&num[3]==0)
            break;
        memset(dp,-1,sizeof(dp));
        dp[0] = 0;
        for (i=0;i<4;i++)
            pack3(v[i],num[i]);
        if (dp[sum] != -1)
        {
            tmp = sum;
            memset(ans,0,sizeof(ans));
            while (tmp!=0)
            {
                k1 = (tmp - fa[tmp])/cnt[tmp];
                if (k1 == 25)
                    ans[3] += cnt[tmp];
                else if (k1 == 10)
                    ans[2] += cnt[tmp];
                else if (k1 == 5)
                    ans[1] += cnt[tmp];
                else
                    ans[0] += cnt[tmp];
                tmp = fa[tmp];
            }
            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[0],ans[1],ans[2],ans[3]);
        }
        else
            printf("Charlie cannot buy coffee.\n");
    }
    return 0;
}