个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
原题链接:点击直接跳转到该题目
1️⃣题目描述
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️⃣解题代码
朴素算法:文章来源:https://www.toymoban.com/news/detail-739657.html
#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;
}
到了这里,关于【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!