最大价值

题目 最大价值

思路分析

第0种物品可以取无限次 第1-m种物品可以取l/h次

所以可以把问题变成 完全背包+多重背包的混合背包问题 也可以直接对0物品进行特判 做多重背包问题

因为数据范围较小 暴力的多重背包也能过

但还是习惯性的写二进制优化吧

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int s[N],v[N],w[N];

int f[N];

int n,m;

int main()

{

    cin>>n>>m>>v[0]>>w[0];

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

        int l,h;

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

        s[i]=l/h;

    }

    //v[0]的完全背包问题

    for(int i=v[0];i<=n;i++)

        f[i]=f[i-v[0]]+w[0];

    //1-m的多重背包问题暴力做法

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

        for(int j=n;j>=0;j--){

            for(int k=1;k<=s[i] && k*v[i]<=j;k++){

                f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);

            }

        }

    }

    cout<<f[n];

    return 0;

}

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int s[N],v[N],w[N];

int f[N];

int cnt;

int n,m;

int main()

{

    cin>>n>>m>>v[0]>>w[0];

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

        int l,h,vi,wi;

        cin>>l>>h>>vi>>wi;

        int k=1,s=l/h;

        while(k<=s){

            cnt++;

            v[cnt]=vi*k;

            w[cnt]=wi*k;

            s-=k;

            k*=2;

        }

        if(s){

            cnt++;

            v[cnt]=vi*s;

            w[cnt]=wi*s;

        }

    }

    //v[0]的完全背包问题

    for(int i=v[0];i<=n;i++)

        f[i]=f[i-v[0]]+w[0];

    //1-m的多重背包问题 01做法

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

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

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

        }

    }

    cout<<f[n];

    return 0;

}

同类题型

视频讲解

⬅️ 庆功会 🏠 00-刷题理模型 ➡️ 单调队列优化多重背包问题