CCF-CSP 37-2（完全背包问题）
#include<iostream> #include<vector> #include<unordered_map> #include<algorithm>//sort排序 using namespace std; //vector数组定义排序 bool compare(pair<int, int> p1, pair<int, int> p2) { return (p1.second / static_cast<double>(p1.first)) > (p2.second / static_cast<double>(p2.first)); } int main() { int n, m; cin >> n >> m; vector<pair<int, int>> arr; for (int i = 1; i <= m; i++) { int cur; cin >> cur; arr.push_back(make_pair(i, cur));//苹果个数：价值 } sort(arr.begin(), arr.end(), compare); int res = 0; int step = 0; while (n != 0) { int num = n / arr[step].first; cout << arr[step].first << endl; if (num == 0) { step++; continue; } n -= num * arr[step].first; res += num * arr[step].second; step++; } cout << res << endl; return 0; }刚开始的想法是用vector数组以：得到价值/投喂个数 作为判断条件价值降序排列，以单个苹果价值高的优先考虑，样例一能够很好的解决但是样例二得到的结果不正确，分析后得到问题这个题目要考虑组合的问题，联想到背包问题，重新进行解决，将苹果个数作为背包容量，价值则为价值。
#include<iostream> #include<vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> arr(m+1);//arr[i]存放大小为i的价值 for (int i = 1; i <= m; i++) { int value; cin >> value; arr[i] = value; } vector<int> dp(n+1,INT_MIN);//dp[i]表示容量为i产生的最大价值 dp[0] = 0; for (int i = 0; i <= n; i++) { if (dp[i] == INT_MIN)continue;//还不能拓展到 //在已知最优解的基础上拓展空间 for (int j = 1; j <= m; j++) { if (i + j > n)continue; if (dp[i + j] < dp[i] + arr[j]) { dp[i + j] = dp[i] + arr[j]; } } } cout << dp[n] << endl; return 0; } 这里需要注意，要从dp[0]开始拓展，我开始用的是dp[1] = arr[1]拓展，但是如果arr[2]>arr[1]+arr[1]就会出现未考虑的错误情况
下面附上回缩式的标准完全背包问题解法：
#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> A(m + 1); A[0] = 0; for (int i = 1; i <= m; ++i) { cin >> A[i]; } //dp表示背包容量为n时最大值为多少 vector<int> dp(n + 1, INT_MIN); dp[0] = 0; for (int j = 1; j <= n; ++j) { for (int i = 1; i <= min(m, j); ++i) { if (dp[j - i] + A[i] > dp[j]) { //如果放入i会使最大值增加则更新 dp[j] = dp[j - i] + A[i]; } } } cout << dp[n] << endl; return 0; }