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;
}

补充：软件开发 , C++ ,