個(gè)人主頁(yè)：兜里有顆棉花糖
歡迎 點(diǎn)贊?? 收藏? 留言? 加關(guān)注??本文由 兜里有顆棉花糖 原創(chuàng)
收錄于專欄【手撕算法系列專欄】【AcWing算法提高學(xué)習(xí)專欄】
??本專欄旨在提高自己算法能力的同時(shí)，記錄一下自己的學(xué)習(xí)過(guò)程，希望對(duì)大家有所幫助
??希望我們一起努力、成長(zhǎng)，共同進(jìn)步。
原題鏈接：點(diǎn)擊直接跳轉(zhuǎn)到該題目
1??題目描述
2??題目解析
狀態(tài)表示：dp[i][j]表示從前i株草藥中進(jìn)行選擇，時(shí)間不超過(guò)j的情況下所能獲得的最大價(jià)值。
狀態(tài)轉(zhuǎn)移方程：
- 不選擇i位置：
dp[i][j] = dp[i - 1][j] - 選擇i位置（前提條件是
j >= V[i]）：dp[i][j] = dp[i - 1][j - V[i]] + W[i]
3??解題代碼
樸素算法：文章來(lái)源：http://www.zghlxwxcb.cn/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;
}
滾動(dòng)數(shù)組空間優(yōu)化：文章來(lái)源地址http://www.zghlxwxcb.cn/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;
}
到了這里，關(guān)于【算法|動(dòng)態(tài)規(guī)劃 | 01背包問(wèn)題No.2】AcWing 423. 采藥的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
