开心的金明

题目 开心的金明

image-64481155

思路分析

裸题

限制条件v变成了价格 权重w变成了重要度

注意这个重要度是需要w[i]=w[i]*v[i]

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=30010;

int v[N],w[N];//此时v为价格（限制条件） w为重要度

int dp[N];

int n,m;

int main()

{

    cin>>m>>n;

    for(int i=1;i<=n;i++){

        cin>>v[i]>>w[i];

        w[i]=w[i]*v[i];

    }

    for(int i=1;i<=n;i++)

        for(int j=m;j>=v[i];j--)

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

    cout<<dp[m];

    return 0;

}

#include<bits/stdc++.h>

using namespace std;

const int N=30010;

int dp[N];

int n,m;

int main()

{

    cin>>m>>n;

    for(int i=1;i<=n;i++){

        int v,w;//vw也可以不用存下来

        cin>>v>>w;

        w=w*v;

        //其实可以合并

        for(int j=m;j>=v;j--)

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

    }

    cout<<dp[m];

    return 0;

}

同类题型

视频讲解

⬅️ 01背包练习 🏠 00-刷题理模型 ➡️ 数字组合