多重背包问题

每个物品有S个，与完全背包不同在于不能选无数个了。

#include<iostream>
#include<vector>

using namespace std;

const int N = 110;
int f[N][N];
int n,m,s;

int main(){
    cin>>n>>m;
    vector<vector<int>> a(n + 1,vector<int> (3));
    
    for(int i = 1;i <= n;i++){
        int v,w,s;
        cin>>v>>w>>s;
        a[i] = {v,w,s};
    }
    
    for(int i = 1; i <= n; i++){
        int v = a[i][0],w = a[i][1], s = a[i][2];

        for(int j = 1; j <= m; j++){
            //不选
            f[i][j] = f[i - 1][j];
            //枚举选多少个
            for(int k = 1; k <= s && k * v <= j; k++){
                f[i][j] = max(f[i][j],f[i - 1][j - k * v] + k * w);
            }
        }
    }
    cout<<f[n][m];
    return 0;
}

可以使用二进制优化，按位取算，但是如果我们使用这样的方式去枚举最后还是O(n ^{3)的，因为这样取枚举只处理一个二进制就需要O(n}2)

for(int i  ~ n)
	//N = 1 << n
	for(j = 1 ~ N)

我们可以这样做，比如物品有10个，我们可以把10拆开，
10 = {1 ， 2 ， 4， 3}
3 = 10 - (1 + 2 +4)
这样括号内的数字可以任意组合而且可以凑成10以内的任何数

这样，把10拆开之后就变成了0-1背包问题。

#include<iostream>
#include<vector>

using namespace std;
typedef pair<int,int> PII;

int n,m;
const int N = 1010 * 2;
int f[N];

int main(){
    cin>>n>>m;
    vector<PII> goods;
    
    for(int i = 1;i <= n;i++){
        int v,w,s;
        cin>>v>>w>>s;
        
        for(int k = 1; k <= s; k *= 2){
            s-=k;
            goods.push_back({k * v, k *w});
        }
        if(s > 0) goods.push_back({s * v, s * w});
    }
    
    for(auto good : goods){
        int v = good.first, w = good.second;
        for(int j = m; j >= v; j--){
            f[j] = max(f[j],f[j - v] + w);
        }
    }
    cout<<f[m];
    return 0;
}