多重背包问题I题目链接

4. 多重背包问题 I - AcWing题库

多重背包问题I题目类型

多重背包问题模板

多重背包问题I题目解析

动态规划

• 状态表示f[i,j]
  • 集合：所有只从前i个物品中选，并且总体积不超过j的选法
  • 属性：Max
• 状态计算
  • f[i] [j] = Max(f[i - 1] [j - v[i] * k] + w[i] * k); k = 0, 1, 2, ..., s[i]

多重背包问题I代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i)
        cin >> v[i] >> w[i] >> s[i];
    
    for(int i=1; i<=n; i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=s[i] && k*v[i]<=j;k++)
                f[i][j] = max(f[i][j], f[i-1][j-v[i]*k]+w[i]*k);
    
    cout<<f[n][m]<<endl;
    return 0;
}

多重背包问题II题目链接

5. 多重背包问题 II - AcWing题库

多重背包问题II题目类型

多重背包问题模板

多重背包问题II题目解析

动态规划

• 状态表示f[i,j]
  • 集合：所有只从前i个物品中选，并且总体积不超过j的选法
  • 属性：Max
• 状态计算
  • f[i] [j] = Max(f[i - 1] [j - v[i] * k] + w[i] * k); k = 0, 1, 2, ..., s[i]

使用二进制优化

时间复杂度：N * log S * V

多重背包问题II代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000, M=2010;

int n, m;
int v[N], w[N];
int f[N];

int main(){
    cin >> n >> m;
    int cnt = 0;
    for(int i=1;i<=n;++i)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k<=s)
        {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s-=k;
            k *=2;
        }
        if(s>0)
        {
            cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    n = cnt;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j], f[j-v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

多重背包问题III题目链接

6. 多重背包问题 III - AcWing题库

多重背包问题III题目类型

多重背包问题模板

多重背包问题III代码

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];
int main(){
    cin >> n >> m;
    for(int i=0;i<n;++i)
    {
        int v, w, s;
        cin>>v>>w>>s;
        memcpy(g, f, sizeof(f));
        for(int j=0;j<v;j++)
        {
            int hh=0, tt=-1;
            for(int k=j;k<=m;k+=v)
            {
                if(hh<=tt&&q[hh]<k-s*v) hh++;
                if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
                while(hh<=tt && g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w) tt--;
                q[++tt]=k;
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}