01背包

Acwing2 01背包

不必装满

 memset(f,0,sizeof(f));
 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]);

恰好装满

memset(f,0x3f,sizeof(f));
f[0] = 0;
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]);

完全背包

Acwing3 完全背包

for(int i = 1; i <= n; i++)
    for(int j = v[i]; j <= m; j++)
        f[j] = max(f[j],f[j-v[i]]+w[i]);

多重背包

Acwing4 多重背包1

朴素版

for(int i = 1; i <= m; i++) {
    int vi,wi,si;
    cin >> vi >> wi >> si;
    for(int j = m; j >= 0; j--)
        for(int k = 1; k <= si && k*vi <= j; k++)
            f[j] = max(f[j],f[j-k*vi]+j*wi);
}

Acwing5 多重背包2

二进制拆分

vector<pair<int,int> > v;
for(int i = 1; i <= n; i++) {
    int vi,wi,si;
    cin >> vi >> wi >> si;
    for(int j = 1; j <= si; j<<=1)
        v.push_back(make_pair(j*vi,j*wi)), si -= j;
    if(si) v.push_back(make_pair(si*vi,si*wi));
}
//01背包
for(int i = 0; i < v.size(); i++)
    for(int j = m; j >= v[i].first; j--)
        f[j] = max(f[j],f[j-v[i].first]+v[i].second);

Acwing6 多重背包3

单调队列优化

// 不会

混合背包

Acwing7 混合背包

//多重背包拆成01背包

for (int i = 1; i <= n; i ++) {
    cin >> V >>  W >> S;
    if ( S == -1 ) v.push_back({0,W,V});
    else if ( S == 0 ) v.push_back({1,W,V});
    else {
        for ( int j = 1; j <= S; j <<= 1 ) {
            v.push_back({0,W*j,V*j});
            S -= j;
        }
        if(S) v.push_back({0,W*S,V*S});
    }
}
for(int i = 0; i < v.size(); i++) {
    if(v[i].k == 0) 
        for(int j = m; j >= v[i].v; j--) 
            f[j] = max(f[j],f[j-v[i].v]+v[i].w);
    else 
        for(int j = v[i].v; j <= m; j++) 
            f[j] = max(f[j],f[j-v[i].v]+v[i].w);
}

二维费用背包

Acwing8 二维费用背包

// 看成01背包

for(int i = 1; i <= n; i++)
    for(int j = M; j >= m[i]; j--)
        for(int k = V; k >= v[i]; k--)
            f[j][k] = max(f[j][k],f[j-m[i]][k-v[i]]+w[i]);

分组背包

Acwing9 分组背包

for(int i = 1; i <= n; i++) // 枚举组数
    for(int j = m; j >= 0; j--) // 枚举体积
        for(int k = 0; k < v.size(); k++) // 枚举选该组的第几个物品
            if(j >= v[k].v)
                f[j] = max(f[j],f[j-v[k].v]+v[k].w);

背包问题求方案数

Acwing11 背包问题求方案数

// 开一个数组来记录方案数

for(int i= 1; i <= n; i++)
    for(int j = m; j >= v[i]; j--) {
        int val = f[j-v[i]]+w[i];
        if(val > f[j]) {
            f[j] = val
            cnt[j] = cnt[j-v[i]];
        } else if(val == f[j]) cnt[j] = cnt[j-v[i]];
    }