【算法|动态规划 | 01背包问题No.1】AcWing 426. 开心的金明

矫情吗；* 2024-04-27 06:50 64阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[AcWing算法提高学习专栏][AcWing]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][530b2fdc59bf45d5bfa43fd373793841.png]

**原题链接：**[点击直接跳转到该题目][Link 3]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

![在这里插入图片描述][12c1f52f333741289cc1eb390b110c92.png]  
![在这里插入图片描述][31e9d9d23ee2483685fbecc39c411795.png]

## 2️⃣题目解析 ##

**状态表示：`dp[i][j]`表示从前`i`个物品中进行挑选且总价钱不超过`j`的情况下，价格与重要度的乘积的总和的最大值。**

**状态转移方程：**

*  **选择第i件物品：**`dp[i][j] = dp[i - 1][j]`
 *  **不选择第i件物品（前提是`j >= V[i]`）：**`dp[i][j] = dp[i - 1][j - V[i]] + V[i] * W[i]`

**注意可以使用滚动数组进行空间优化，填表时需要从右往左进行填表。**

## 3️⃣解题代码 ##

**朴素算法：**

#include<iostream>
    using namespace std;
    
    const int M = 26;
    const int N = 30000;
    int dp[M][N],V[M],W[M];
    
    int main()
    {
        
        int n,m;
        cin >> n >> m;
        for(int i = 1;i <= n;i++) cin >> V[i] >> W[i];
        for(int i = 1;i <= m;i++)
        {
        
            for(int j = 1;j <= n;j++)
            {
        
                dp[i][j] = dp[i - 1][j];
                if(j - V[i] >= 0) dp[i][j] = max(dp[i][j],dp[i - 1][j - V[i]] + V[i] * W[i]);
            }
        }
        cout << dp[m][n] << endl;
    }

**滚动数组进行空间优化代码：**

#include<iostream>
    using namespace std;
    
    const int M = 26;
    const int N = 30000;
    int dp[N],V[M],W[M];
    
    int main()
    {
        
        int n,m;
        cin >> n >> m;
        for(int i = 1;i <= n;i++) cin >> V[i] >> W[i];
        for(int i = 1;i <= m;i++)
        {
        
            for(int j = n;j >= V[i];j--)
            {
        
                dp[j] = max(dp[j],dp[j - V[i]] + V[i] * W[i]);
            }
        }
        cout << dp[n] << endl;
    }

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[AcWing]: https://blog.csdn.net/m0_74352571/category_12481646.html?spm=1001.2014.3001.5482
[530b2fdc59bf45d5bfa43fd373793841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/0ad8373449914476b8e0320adf890d7f.png
[Link 3]: https://www.acwing.com/problem/content/description/428/
[12c1f52f333741289cc1eb390b110c92.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/4f1f1951af34457283c657f95f60fe26.png
[31e9d9d23ee2483685fbecc39c411795.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/a4a2e03ff08e44e685a0907fabc71396.png