基本思想:
总结过;
关键点:
无;
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int maxn = 10000; int c, n; int dp[maxn]; int w[maxn]; int p[maxn]; int main() { while (cin >> c >> n) { for (int i = 1; i <= n; i++) { cin >> p[i] >> w[i]; } for (int i = 0; i <= c; i++) { dp[i] = 0; } for (int i = 1; i <= n; i++) { for (int j = c; j >= p[i]; j--) { dp[j] = max(dp[j], dp[j - p[i]] + w[i]); } } cout << dp[c]<<endl; } }
北京大学机试 点菜问题 需要二刷 *经典01背包问题,注意一下
原文:https://www.cnblogs.com/songlinxuan/p/12631043.html