编写题解 1103: 开心的金明

解题思路:背包问题、vector、动态规划dp

注意事项:

参考代码:

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int main()

{

    int n,m;

    cin>>n>>m;

    vector<pair<int ,int >>myvector(m);

    sort(myvector.begin(),myvector.end());

    vector<int>dp(n+1,0);

    for(int i=0;i<m;i++){

        cin>>myvector[i].first>>myvector[i].second;

        myvector[i].second*=myvector[i].first;

}

    sort(myvector.begin(),myvector.end());

        for(int i=0;i<m;i++){

        for(int k=n;k>=myvector[i].first;k--){

            dp[k]=max(dp[k],dp[k-myvector[i].first]+myvector[i].second);

        }

}

        int sum_max=0;

        for(int k=0;k<=n;k++){

            sum_max=max(sum_max,dp[k]);

        }

        cout<<sum_max;

}