多重背包问题

题目题面

有 N种物品和一个容量是 V的背包。

第 i种物品最多有 si件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

数据范围

0< N , V ≤ 10000
0 < vi , wi , si≤ 10000

解法1(朴素算法)

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;

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

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

解法2(二进制优化)

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, k;
int f[N], v[N], w[N];

int main()
{
	cin >> n >> m;
    for(int i = 0;i < n;i++) {
		int a, b, c;
        cin >> a >> b >> c;
        int s = 1;
        while(s <= c) {
            k++;
            v[k] = s * b;
            w[k] = s * a;
            c -= s;
            s *= 2;
        }
        if(c > 0) {
            k++;
            v[k] = c * b;
            w[k] = c * a;
        }
    }
    for(int i = 0;i < k;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;
}

解法3(优先队列优化)

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int f[N], t[N], q[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        memcpy(t, f, sizeof(f));
        //体积 价值 数量
        int v, w, s;
        cin >> v >> w >> s;
        //体积遍历
        for (int j = 0; j < v; j++) {
            //队列
            int hh = 0, tt = -1;
            //每一个目前体积算到最大价值
            for (int k = j; k <= m; k += v) {
                //队列不为空同时目前价值 > 最大价值 
                if (hh <= tt && k - s*v > q[hh]) hh++;
                //队列遍历出大于目前体积的价值
                while (hh <= tt && t[q[tt]] - (q[tt] - j)/v * w <= t[k] - (k - j)/v * w) tt--;
                //队列不为空，说明找到了新的最大价值 / 最大价值不变
                if (hh <= tt) f[k] = max(f[k], t[q[hh]] + (k - q[hh])/v * w);
                //加入队列
                q[++tt] = k;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}