AcWing 开心的金明【 01背包问题】 c++详细题解

比眉伴天荒 2021-07-25 00:32 585阅读 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