【Luogu1048】采药

            

题面

01背包
注意输入线体积再物品个数

题解

//f[i][j]:当前在选第i个物品,剩余体积为j时能获得的最大价值。
#include
using namespace std;
const int maxn = 1010;
int n, m, w[maxn], v[maxn], f[maxn][maxn];
int main(){
    cin>>m>>n;
    for(int i = 1; i <= n; i++)
        cin>>w[i]>>v[i];
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            if(j>=w[i])f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
            else f[i][j] = f[i-1][j];
    cout<"\n";
    return 0;
}
//f[i]:剩余体积为i时能获得的最大价值
#include
#include
using namespace std;
const int maxn = 5010;
int n, m, w[maxn], v[maxn], f[maxn];
int main(){
    cin>>m>>n;
    for(int i = 1; i <= n; i++)
        cin>>w[i]>>v[i];
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= w[i]; j--)
            f[j] = max(f[j],f[j-w[i]]+v[i]);
    cout<"\n";
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像