HDOJ4501 小明系列故事——買年貨（動態規劃）&& 騰訊2013編程馬拉松第0場第

多維動態規劃，背包變形，題目代碼比較簡單，講解寫在代碼注釋裡

[cpp]
/*HDOJ4501 && 騰訊2013編程馬拉松第1場第二題
作者：陳佳潤
2013-04-15
*/ 
#include<iostream>  
using namespace std; 
int V1,V2,K; 
int dp[101][101][6]; 
 
int max(int a,int b){ 
    if(a>b) 
        return a; 
    return b; 
} 
 
void MZO(int v1,int v2,int v){//三維0/1背包  
    int i,j,k; 
     
    for(i=V1;i>=0;i--){//注意此處跟背包的不一樣，如果寫成i>=v1,j>=v2,k>=1,則是需要三個同時成立  
        for(j=V2;j>=0;j--){//寫成>=0,然後再用if判斷則可以達到三者其中之一成立就可以購買  
            for(k=K;k>=0;k--){ 
                int temp=0; 
                if(i>=v1) temp=max(temp,dp[i-v1][j][k]+v); 
                if(j>=v2) temp=max(temp,dp[i][j-v2][k]+v); 
                if(k>0) temp=max(temp,dp[i][j][k-1]+v); 
                dp[i][j][k]=max(dp[i][j][k],temp); 
            } 
        } 
    } 
} 
 
int main(){ 
    int n,i,v1,v2,v; 
    //freopen("1.txt","r",stdin);  
    while(cin>>n>>V1>>V2>>K){ 
        memset(dp,0,sizeof(dp)); 
        for(i=1;i<=n;i++){ 
            cin>>v1>>v2>>v; 
            MZO(v1,v2,v); 
        } 
        cout<<dp[V1][V2][K]<<endl; 
    } 
    return 0; 
} 

/*HDOJ4501 && 騰訊2013編程馬拉松第1場第二題
作者：陳佳潤
2013-04-15
*/
#include<iostream>
using namespace std;
int V1,V2,K;
int dp[101][101][6];

int max(int a,int b){
 if(a>b)
  return a;
 return b;
}

void MZO(int v1,int v2,int v){//三維0/1背包
 int i,j,k;
 
 for(i=V1;i>=0;i--){//注意此處跟背包的不一樣，如果寫成i>=v1,j>=v2,k>=1,則是需要三個同時成立
  for(j=V2;j>=0;j--){//寫成>=0,然後再用if判斷則可以達到三者其中之一成立就可以購買
   for(k=K;k>=0;k--){
    int temp=0;
    if(i>=v1) temp=max(temp,dp[i-v1][j][k]+v);
    if(j>=v2) temp=max(temp,dp[i][j-v2][k]+v);
    if(k>0) temp=max(temp,dp[i][j][k-1]+v);
    dp[i][j][k]=max(dp[i][j][k],temp);
   }
  }
 }
}

int main(){
 int n,i,v1,v2,v;
 //freopen("1.txt","r",stdin);
 while(cin>>n>>V1>>V2>>K){
  memset(dp,0,sizeof(dp));
  for(i=1;i<=n;i++){
   cin>>v1>>v2>>v;
   MZO(v1,v2,v);
  }
  cout<<dp[V1][V2][K]<<endl;
 }
    return 0;
}