HDOJ 1114 Piggy-Bank （多重背包）

恰好裝滿的多重背包

初始化時，將dp都初始化成無窮大，而dp[0]=0；即可

[cpp]
/*HDOJ1114
作者：陳佳潤
2013-04-18
*/ 
#include<iostream>  
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."<<endl; 
        else 
            cout<<"The minimum amount of money in the piggy-bank is "<<dp[Weight]<<"."<<endl; 
    } 
    return 0; 
} 

/*HDOJ1114
作者：陳佳潤
2013-04-18
*/
#include<iostream>
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."<<endl;
  else
   cout<<"The minimum amount of money in the piggy-bank is "<<dp[Weight]<<"."<<endl;
 }
 return 0;
}