【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

素颜马尾好姑娘i 2024-04-27 06:50 80阅读 0赞

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

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

#### 目录 ####

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

## 1️⃣题目描述 ##

![在这里插入图片描述][6207f21daada4f2ab3cb9fd7786d93ad.png]  
![在这里插入图片描述][60180fbac9c349b69f58f14689c7589d.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]] + W[i]`**

## 3️⃣解题代码 ##

**朴素算法：**

#include<iostream>
    using namespace std;
    const int M = 110, T = 1010;
    int dp[M][T],V[M],W[M];
    
    int main()
    {
        
        int t,m;
        cin >> t >> m;
        for(int i = 1;i <= m;i++) cin >> V[i] >>W[i];
        for(int i = 1;i <= m;i++)
        {
        
            for(int j = 1;j <= t;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]] + W[i]);
            }
        }
        cout << dp[m][t];
        return 0;
    }

**滚动数组空间优化：**

#include<iostream>
    using namespace std;
    
    const int M = 110, T = 1010;
    int dp[T],V[M],W[M];
    
    int main()
    {
        
        int t,m;
        cin >> t >> m;
        for(int i = 1;i <= m;i++) cin >> V[i] >>W[i];
        for(int i = 1;i <= m;i++)
        {
        
            for(int j = t;j >= V[i];j--)
            {
        
                if(j - V[i] >= 0) dp[j] = max(dp[j],dp[j - V[i]] + W[i]);
            }
        }
        cout << dp[t];
        return 0;
    }

[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/12751cda50c64cd387dcf71af3b7a71a.png
[Link 3]: https://www.acwing.com/problem/content/425/
[6207f21daada4f2ab3cb9fd7786d93ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/f0d3e507855745cda1a4e5cc474f7f98.png
[60180fbac9c349b69f58f14689c7589d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/a9fd1faf6a5447ee933d67892d047ddf.png