采药

采药

http://www.nowcoder.com/questionTerminal/d7c03b114f0541dd8e32ce9987326c16

思路

这个和 点菜问题 一样,也是 0-1 背包问题,这里就不进行赘述了,用 dp[i][j] 表示限时 j 采前 i 种药的最大总价值,那最后求出来 dp[M][T] 就好了

  • 不采第 i 种药:
  • 采第 i 种药:

因为前面已经说过如果进行空间复杂度的优化,这里我就直接写出优化后的版本了。

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int T, M;
    while(cin >> T >> M){
        vector<pair<int, int>> herbs;
        int time, value;
        for(int i = 0; i < M; i ++){
            cin >> time >> value;
            herbs.emplace_back(time, value);
        }
        vector<int> dp(T + 1, 0);
        for(int i = 0; i < M; i ++){
            for(int j = T; j >= herbs[i].first; j --)
                dp[j] = max(dp[j], dp[j - herbs[i].first] + herbs[i].second);
        }
        cout << dp[T] << endl;
    }
    return 0;
}
算法题解 文章被收录于专栏

不定期更新一些算法题解,有什么问题可以随时留言~

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 13:05
点赞 评论 收藏
分享
点赞 评论 收藏
分享
下个早班:秒挂就是不缺人
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务