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

这篇具有很好参考价值的文章主要介绍了【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

个人主页：兜里有颗棉花糖
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由兜里有颗棉花糖原创
收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

原题链接：点击直接跳转到该题目

1️⃣题目描述

【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药,手撕算法系列专栏,AcWing算法提高学习专栏,算法,动态规划

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;
}

滚动数组空间优化：文章来源地址https://www.toymoban.com/news/detail-739657.html

#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;
}