HDOJ 1114 Piggy-Bank （多重背包）

恰好装满的多重背包

初始化时，将dp都初始化成无穷大，而dp[0]=0；即可

[cpp]
/*HDOJ1114
作者：陈佳润
2013-04-18
*/
#include
using namespace std;
#define min(a,b) (a>b b:a)
#define INF 0x3f3f3f3f
int dp[10005];
int Weight;
int n;

void Multipy_Pack(int value,int weight){
int i;
for(i=weight;i<=Weight;i++){
dp[i]=min(dp[i],dp[i-weight]+value);
}
}

int main(){
int Time,WeightOfAll,WeightOfPig,i,value,weight;
//freopen("1.txt","r",stdin);
cin>>Time;
while(Time--){
cin>>WeightOfPig>>WeightOfAll;
Weight=WeightOfAll-WeightOfPig;
cin>>n;
memset(dp,INF,sizeof(dp));
dp[0]=0;
for(i=1;i<=n;i++){
cin>>value>>weight;
Multipy_Pack(value,weight);
}
if(dp[Weight]==INF)
cout<<"This is impossible."< else
cout<<"The minimum amount of money in the piggy-bank is "< }
return 0;
}

/*HDOJ1114
作者：陈佳润
2013-04-18
*/
#include
using namespace std;
#define min(a,b) (a>b b:a)
#define INF 0x3f3f3f3f
int dp[10005];
int Weight;
int n;

void Multipy_Pack(int value,int weight){
int i;
for(i=weight;i<=Weight;i++){
dp[i]=min(dp[i],dp[i-weight]+value);
}
}

int main(){
int Time,WeightOfAll,WeightOfPig,i,value,weight;
//freopen("1.txt","r",stdin);
cin>>Time;
while(Time--){
cin>>WeightOfPig>>WeightOfAll;
Weight=WeightOfAll-WeightOfPig;
cin>>n;
memset(dp,INF,sizeof(dp));
dp[0]=0;
for(i=1;i<=n;i++){
cin>>value>>weight;
Multipy_Pack(value,weight);
}
if(dp[Weight]==INF)
cout<<"This is impossible."< else
cout<<"The minimum amount of money in the piggy-bank is "< }
return 0;
}