采药

题目 采药

思路分析

比较裸的01背包

时间T就是容积v 草药数M就是物品数n

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int v[N],w[N];

int dp[N];

int T,M;

int main()

{

    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--){

            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

        }

    }

    cout<<dp[T];

    return 0;

}

同类题型

视频讲解

⬅️ 装箱问题 🏠 00-刷题理模型 ➡️ 01背包问题