CCF-CSP 37-2（完全背包问题）

#includeiostream #includevector #includeunordered_map #includealgorithm//sort排序 using namespace std; //vector数组定义排序 bool compare(pairint, int p1, pairint, int p2) { return (p1.second / static_castdouble(p1.first)) (p2.second / static_castdouble(p2.first)); } int main() { int n, m; cin n m; vectorpairint, 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数组以得到价值/投喂个数 作为判断条件价值降序排列以单个苹果价值高的优先考虑样例一能够很好的解决但是样例二得到的结果不正确分析后得到问题这个题目要考虑组合的问题联想到背包问题重新进行解决将苹果个数作为背包容量价值则为价值。​ #includeiostream #includevector using namespace std; int main() { int n, m; cin n m; vectorint arr(m1);//arr[i]存放大小为i的价值 for (int i 1; i m; i) { int value; cin value; arr[i] value; } vectorint dp(n1,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; vectorint A(m 1); A[0] 0; for (int i 1; i m; i) { cin A[i]; } //dp表示背包容量为n时最大值为多少 vectorint 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; }