HDU3591 The trouble of Xiaoqian

这题一看 就知道 是 完全背包和多重背包的结合题目了;

对于买东西的是多重背包,商店是完全背包;

这里要用到背包的初始化问题,因为求最小,所以初值要尽量大,大于所有可能的最大值;

值得一提的是背包上限是20000,不是读入的T;

用两个数组分别记录需要用到的最少货币数,一维就够用了;

多重的单调队列好难不懂..只会用二进制优化过的多重背包;

下面给出代码:

#include<iostream>
#include<algorithm>
#define maxn  100010
#define min(a,b) (a>b?b:a)
int v[maxn],c[maxn],f[maxn],g[maxn],n,t;
using namespace std;
int main()
{
    int count=0;
    //freopen("3591.txt","r",stdin);
    while(~scanf("%d %d",&n,&t),n,t)
    {
        int i,j,k;
        for(i=0;i<n;i++)
            scanf("%d",v+i);
        for(i=0;i<n;i++)
            scanf("%d",c+i);
        for(i=1;i<maxn;i++)
            f[i]=g[i]=maxn;
        f[0]=g[0]=0;
        for(i=0;i<n;i++)
        {
            if(v[i]*c[i]>=20000)//完全背包
            {
                for(j=v[i];j<=20000;j++)
                    f[j]=min(f[j],f[j-v[i]]+1);
                continue;
            }
            k=1;
            while(k<c[i])//0-1 背包
            {
                for(j=20000;j>=k*v[i];j--)
                    f[j]=min(f[j],f[j-k*v[i]]+k);
                c[i]-=k;
                k*=2;
            }
            for(j=20000;j>=c[i]*v[i];j--)
                f[j]=min(f[j],f[j-c[i]*v[i]]+c[i]);
        }
        for(i=0;i<n;i++)
          for(j=v[i];j<=20000;j++)
                g[j]=min(g[j],g[j-v[i]]+1);
        int ans=maxn;
        for(i=t;i<=20000;i++)
        {
            if(ans>f[i]+g[i-t])
                ans=f[i]+g[i-t];
        }
        if(ans==maxn) ans=-1;
        printf("Case %d: %d
",++count,ans);
    }
    return 0;
}