0/1背包

wangbinfeng · 2021-08-21 17:18:34 · 算法·理论

//by wangbinfeng
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[1100],t[110],mo[110],n,m;
int main(){
    cin>>n>>m;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=m;i++)cin>>t[i]>>mo[i];
    for(int i=1;i<=m;i++){
        for(int j=n;j>=t[i];j--){
            dp[j]=max(dp[j],dp[j-t[i]]+mo[i]);
        }
    }
    cout<<dp[n];
}