hdu3591The trouble of Xiaoqian【多重背包】
Problem Description
In the country of ALPC , Xiaoqian is a very famous mathematician. She is immersed in calculate, and she want to use the minimum number of coins in every shopping. (The numbers of the shopping include the coins she gave the store and the store backed to her.)
And now , Xiaoqian wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, ..., VN (1 ≤ Vi ≤ 120). Xiaoqian is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner .But Xiaoqian is a low-pitched girl , she wouldn’t like giving out more than 20000 once.
And now , Xiaoqian wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, ..., VN (1 ≤ Vi ≤ 120). Xiaoqian is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner .But Xiaoqian is a low-pitched girl , she wouldn’t like giving out more than 20000 once.
Input
There are several test cases in the input.
Line 1: Two space-separated integers: N and T.
Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN)
Line 3: N space-separated integers, respectively C1, C2, ..., CN
The end of the input is a double 0.
Line 1: Two space-separated integers: N and T.
Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN)
Line 3: N space-separated integers, respectively C1, C2, ..., CN
The end of the input is a double 0.
Output
Output one line for each test case like this ”Case X: Y” : X presents the Xth test case and Y presents the minimum number of coins . If it is impossible to pay and receive exact change, output -1.
Sample Input
3 70 5 25 50 5 2 1 0 0
Sample Output
Case 1: 3
这个题应该是多重背包要刷的第一个题，前几天看他有点难刷了前几个水题，今天看他恍然大悟，明晃晃的多重背包+完全背包 找钱用完全背包 从t到20000扫一遍找最小值呗
然而事情远没有那么顺利==第一次交WA发现中间变量忘记注释，第二次WA发现自己没输出格式Case i……后来是发现k倍之后就不再是+1而是+k了，再后来发现根本用不着四个数组==之前好像也是找钱之类的场景，要求输出正好的解，只是初始化的时候做了处理，并不用再设两个数组，典型的熊瞎子掰苞米……
/***********
hdu3519
2015.11.3
46MS 1872K 2297 B
***********/
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 20000
int dp1[maxn+6],value[105],num[105],t,n,dp2[maxn+6];//钱币个数
int f1[maxn+6],f2[maxn+6];//钱数
void zeropack(int cost,int value,int k)
{
for(int i=maxn;i>=cost;i--)
{
if(dp1[i-cost]!=-1&&(dp1[i-cost]+k<dp1[i]||dp1[i]==-1))
dp1[i]=dp1[i-cost]+k;
}
// cout<<"01"<<endl;
}
void completepack(int cost,int value)
{
for(int i=cost;i<=maxn;i++)
{
if(dp1[i-cost]!=-1&&(dp1[i-cost]+1<dp1[i]||dp1[i]==-1))
dp1[i]=dp1[i-cost]+1;
// f1[i]=max(f1[i],f1[i-cost]+value);
}
//cout<<"complete"<<endl;
}
void multipack(int cost,int value,int num)
{
if(num*cost>=maxn)
{
completepack(cost,value);
return;
}
int k=1;
while(k<num)
{
zeropack(k*cost,k*value,k);
num-=k;
k*=2;
}
zeropack(num*cost,num*value,k);
}
int main()
{
// freopen("cin.txt","r",stdin);
int cnt=1;
while(~scanf("%d%d",&n,&t))
{
if(t==0&&n==0) break;
for(int i=1;i<=n;i++) scanf("%d",&value[i]);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
memset(dp2,-1,sizeof(dp2));
memset(dp1,-1,sizeof(dp1));
memset(f1,0,sizeof(f1));
memset(f2,0,sizeof(f2));
dp2[0]=0;dp1[0]=0;
for(int i=1;i<=n;i++)
for(int j=value[i];j<=maxn;j++)
{
if(dp2[j-value[i]]!=-1&&(dp2[j]<dp2[j-value[i]]+1||dp2[j]==-1))
dp2[j]=dp2[j-value[i]]+1;
// f2[j]=max(f2[j],f2[j-value[i]]+value[i]);
}
for(int i=1;i<=n;i++)
{
multipack(value[i],value[i],num[i]);
}
// for(int i=70;i<=80;i++) printf("f1=%d f2=%d dp1=%d dp2=%d\n",f1[i],f2[i],dp1[i],dp2[i]);
int minn=0x3f3f3f3f;
for(int i=t;i<=maxn;i++)
{
//if(f1[i]!=i||f2[i-t]!=i-t) continue;
if(dp1[i]!=-1&&dp2[i-t]!=-1)
minn=min(minn,dp1[i]+dp2[i-t]);
}
if(minn!=0x3f3f3f3f)
printf("Case %d: %d\n",cnt++,minn);
else printf("Case %d: -1\n",cnt++);
}
return 0;
}
