纯0-1背包问题

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compre(const vector<int>& a,const vector<int>& b){
    return a[0]<b[0];
}

int main()
{
    int t,m;
    cin>>t>>m;
    vector<vector<int>> list;
    while(m--){
        int st,v;
        cin>>st>>v;
        list.push_back({st,v});
    }
    //先排序
    sort(list.begin(),list.end(),compre);
    //表示时间i对应的最高价值
    int dp[1001]={0};
    //0时刻价值0
    dp[0]=0;
    //0-1
    for(int i=0;i<list.size();i++){
        int st=list[i][0];
        int v=list[i][1];
        //如果把这个for放外面就是无限取
        for(int j=t;j>=st;j--){
            dp[j]=max(dp[j-st]+v,dp[j]);
        }
    }
    cout<<dp[t]<<endl;
    return 0;
}