题目描述

01背包+滚动数组

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e3+5;
int dp[maxn];
int t,m;
int main(){
    cin>>t>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        for(int j=t;j-x>=0;j--){
            dp[j]=max(dp[j],dp[j-x]+y);
        }
    }
    cout<<dp[t]<<endl;
    return 0;
}