蓝桥杯算法提高VIP-求最大值-题解（C++代码）

解题思路:

1.固定a的和，在这种组合下找出b最大的和

2.dp[i][j]在前i种的情况下,a的和为j,b的和最大为dp[i][j]

3.状态转移方程式 dp[i][j]=max(  dp[i-1][j](没选a[i]) ，dp[i-1][j-a[i]](选了a[i])  )

注意事项:a的和有可能为负数，下标不能表示负数，对a的和偏移100000，最后结果减去100000

参考代码:

#include<cstdio>
#include<iostream>
#include<string.h>
#define INF 0x6666
#define N 100000
using namespace std;
int n,a[105],b[105],dp[101][2*N+8];
int ans;
void init(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        a[i]=x,b[i]=y;
    }
}//输入数据

void f(){
    memset(dp,-INF,sizeof(dp));
    for(int i=1;i<=n;i++)dp[i][a[i]+N]=b[i];
    for(int i=2;i<=n;i++){
        for(int j=0;j<=2*N;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
            if(j-a[i]<0)continue;
            if(j-a[i]>2*N)break;//此时的j-a[i]大于了20w,证明a[i]<0,可以跳出内层循环
            dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]+b[i]);
        }
    }
    ans=0;//总和最小的和为0
    for(int i=N;i<=2*N;i++){
        if(dp[n][i]>=0)ans=max(ans,dp[n][i]+i-N);
    }
}//动态规划的函数

int main(){
    init();
    f();
    if(ans==0)cout<<"0";
    else cout<<ans;
    return 0;
}