AcWing 开心的金明 【 01背包问题 】 c++详细题解 比眉伴天荒 2021-07-25 00:32 498阅读 0赞 ### 目录 ### * * * 题目 * 二维DP * 一维DP ### 题目 ### 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。 更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。 今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N元。 于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。 他还从因特网上查到了每件物品的价格(都是整数元)。 他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为v\[j\],重要度为w\[j\],共选中了k件物品,编号依次为j1,j2,…,jk,则所求的总和为: v\[j1\]∗w\[j1\]+v\[j2\]∗w\[j2\]+…+v\[jk\]∗w\[jk\] 请你帮助金明设计一个满足要求的购物单。 **输入格式** 输入文件的第1行,为两个正整数N和m,用一个空格隔开。(其中N表示总钱数,m为希望购买物品的个数) 从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数v和p。(其中v表示该物品的价格,p表示该物品的重要度) **输出格式** 输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(数据保证结果不超过100000000)。 **数据范围** 1≤N<30000, 1≤m<25, 0≤v≤10000, 1≤p≤5 **输入样例:** 1000 5 800 2 400 5 300 5 400 3 200 2 **输出样例:** 3900 ### 二维DP ### **闫氏DP分析法** -------------------- **图示:** ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70] -------------------- **状态计算:** `f[i][j]` 表示所有从前`i`个物品选,且总体积不超过`j`的选法集合中的价值最大值 那么`f[n][m]`就表示从前`n`种物品中选,且总体积不超过为`m`的所有选法集合的价值最大值,即为答案。 **集合划分:** 按照第`i`种物品选或者不选划分 `f[i][j]`集合。 不选第`i`种物品,`f[i][j] = f[i-1][j];` 问题转化为从前`i-1`个物品选,且总体积不超过`j`的选法集合中的最大值。 选第`i`种物品, `f[i][j] = f[i-1][j-v] + v*w ;` 已经确定选第`i`种物品,那么问题转化为从前`i-1`个物品选,且总体积不超过`j-v`的选法集合中的最大值再加上 `v*w`。 **状态计算方程:** **ac代码:** #include <iostream> #include <cstdio> using namespace std; const int N = 3e4 + 10,M = 30; int v[M], w[M]; int f[M][N]; int n, m; int main() { cin >> m >> n; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i++) { for(int j = 0; j <= m; j++) { f[i][j] = f[i-1][j]; if(j>=v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+v[i]*w[i]); } } cout << f[n][m] << endl; return 0; } ### 一维DP ### **考虑优化** 状态计算时`f[i]`层的更新只用到了`f[i-1]`层,我们去掉前一维 **状态计算方程为 :**`f[j] = max(f[j], f[j-v]+v*w);` **代码表示:** for(int j = v[i]; j <= m; j++) { f[j] = max(f[j], f[j-v[i]]+v[i]*w[i]); } 此时不和之前的代码等价了,因为在计算第`i`层的状态时,我们从小到大枚举体积,体积 `j-v[i]`严格小于`j`,那么`f[j-v[i]]`会先于`f[j]`被计算出来,此时我们计算出来的`f[j-v[i]]`仍为第`i`层状态,这样`f[j-v[i]]`等价于`f[i][j-v[i]]` ,实际上`f[j-v[i]]`应该等价于`f[i-1][j-v[i]]`。 **为了解决这个问题只需要体积从大到小枚举,** for(int j = m ; j >= v[i]; j--) { f[j] = max(f[j], f[j-v[i]]+v[i]*w[i]); } 因为我们从大到小枚举体积,而 `j - v[j]`严格小于`j`,我们在计算`f[j`\] 的时候`f[j-v[i]]`还未被第`i`层状态更新过,那么它存的就是上一层(`i-1`层)的状态,即`f[i-1][j-v[i]]`。 **ac代码** #include <iostream> #include <algorithm> using namespace std; const int N = 3e5 + 10; int n, m; int f[N]; int main() { cin >> m >> n; for (int i = 0; i < n; i ++ ) { int v, w; cin >> v >> w; for (int j = m; j >= v; j -- ) //体积从大往小枚举 f[j] = max(f[j], f[j - v] + w*v); } cout << f[m] << endl; return 0; } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/870644be378a495ebe8730b5d4a00699.png
还没有评论,来说两句吧...