今日头条第三题 dp解 扩展的背包问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int n;
int x[105],y[105];
int max_score;

int main(){
    while(scanf("%d",&n)!=EOF){
        int x_sum = 0;
        for(int i=0;i<n;i++){
            scanf("%d%d",x+i,y+i);
            x_sum += x[i];
        }
        vector<vector<int>> dp(x_sum+1,vector<int>(x_sum+1,INF));
        dp[0][0] = 0;
        for(int i=0;i<n;i++){  //考虑每个物品
            for(int j=x_sum;j>=0;j--){
                for(int k=x_sum;k>=0;k--){
                    int t=-1;
                    if(j-x[i]>=0 && dp[j-x[i]][k]!=INF)
                        t = max(t,dp[j-x[i]][k]);
                    if(k-x[i]>=0 && dp[j][k-x[i]]!=INF)
                        t = max(t,dp[j][k-x[i]]);
                    if(t!=-1)
                        t += y[i];
                    if(t!=-1){
                        if(dp[j][k] == INF)
                            dp[j][k] = t;
                        else
                            dp[j][k] = max(dp[j][k],t);
                    }
//                    dp[j][k] = max(max(dp[j-x[i]][k],dp[j][k-x[i]])+y[i],dp[j][k]);
                }
            }
        }
        for(int i=0;i<=x_sum;i++)
            if(dp[i][i]!=INF)
                max_score = max(max_score,dp[i][i]);
        printf("%d\n",max_score);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;
int n;
int x[105],y[105];
int max_score;
void dfs(int idx,int a,int b,int team){
    if(idx==n){
        if(team>max_score && a==b){
            max_score = team;
        }
        return ;
    }
    //对于一个牌，有a取，b取和都不取三种选择
    dfs(idx+1,a+x[idx],b,team+y[idx]);  //a取
    dfs(idx+1,a,b+x[idx],team+y[idx]);
    dfs(idx+1,a,b,team);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%d%d",x+i,y+i);
        max_score = 0;
        dfs(0,0,0,0);
        printf("%d\n",max_score);
    }
    return 0;
}