HDOJ 1248 寒冰王座 （多重背包）

標准的多重背包，直接附代碼：

[cpp]
/*HDOJ1248
作者：陳佳潤
2013-04-18
*/  
#include<iostream>  
#include<string.h>  
using namespace std; 
#define max(a,b) (a>b?a:b)  
int dp[10005]; 
int momey; 
 
void Multiply_Pack(int value,int weight){ 
    int i; 
    for(i=weight;i<=momey;i++){ 
        dp[i]=max(dp[i],dp[i-weight]+value);  
    }  
} 
 
int main(){ 
    int Time; 
    cin>>Time; 
    while(Time--){ 
        cin>>momey;    
        memset(dp,0,sizeof(dp)); 
        Multiply_Pack(150,150); 
        Multiply_Pack(200,200); 
        Multiply_Pack(350,350); 
        cout<<momey-dp[momey]<<endl; 
    } 
    return 0; 
} 

/*HDOJ1248
作者：陳佳潤
2013-04-18
*/
#include<iostream>
#include<string.h>
using namespace std;
#define max(a,b) (a>b?a:b)
int dp[10005];
int momey;

void Multiply_Pack(int value,int weight){
 int i;
 for(i=weight;i<=momey;i++){
  dp[i]=max(dp[i],dp[i-weight]+value);
 }
}

int main(){
 int Time;
 cin>>Time;
 while(Time--){
  cin>>momey; 
  memset(dp,0,sizeof(dp));
  Multiply_Pack(150,150);
  Multiply_Pack(200,200);
  Multiply_Pack(350,350);
  cout<<momey-dp[momey]<<endl;
 }
 return 0;
}