2.16 背包学习

11. 背包问题求方案数

思路

求最优方案数可以分成两步
第一步求出最优方案，也就是最大价值
第二部求最大价值下的方案数具体有多少种

而求出当前i,j下最大价值，然后求出相应的方案数即可一步步递推出最终结果

集合划分：
当前最大价值f[i, j]若是等于f[i - 1, j]，那么相应方案一定从它转化而来，cnt += g[i - 1, j]
若是等于f[i - 1, j - v] + w，相应方案一定从它转化过来，cnt += g[i - 1, j - v]
若是两种价值相等，说明相应方案可以从这两种价值对应的方案同时转化过来也就可以两个同时加上

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

using namespace std;

const int N = 1010, mod = 1e9 + 7;
int f[N];                         //记录最大价值
int g[N];                         //记录方案数
int n, m;

int main() {
    cin >> n >> m;
    
    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    //上面两行不加也可以，因为0就已经相当于没有价值，求最大值可以不用加上负无穷，但是求最小值必须赋值正无穷
    g[0] = 1;
    for (int i = 1; i <= n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j --) {
            int maxv = max(f[j], f[j - v] + w);
            int cnt = 0;
            if (maxv == f[j]) cnt += g[j];
            if (maxv == f[j - v] + w) cnt += g[j - v];
            g[j] = cnt % mod;
            f[j] = maxv;
        }
    }
    
    int res = 0, cnt = 0;
    for (int i = 0; i <= m; i ++) res = max(res, f[i]);    //找到最优解
    for (int i = 0; i <= m; i ++) {
        if (res == f[i]) {
            cnt = (cnt + g[i]) % mod;                      //对最优解的方案数加和
        }
    }
    
    cout << cnt << endl;
    return 0;
}

734. 能量石

思路

贪心 + dp
在dp之前，需要从题目中找到某些性质，可以使题目通过某种变化变成可以使用dp解决
本题性质为对于任意两个石头，si * li+1 < si+1 * li
然后就是01背包求最大价值
这题集合划分依据为恰好等于体积j的，所以需要赋值负无穷
因为不是最多为j的最大价值，所以需要遍历数组f，找到最大价值

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

using namespace std;

const int N = 100010, M = 110;
int f[N];

struct Stone {
    int s, e, l;
    bool operator < (const Stone &W) const {       //重载<运算符 令顺序为si * li+1 < si+1 * li
        return s * W.l < W.s * l;
    }
}stone[M];

int main() {
    int T;
    cin >> T;
    for (int H = 1; H <= T; H ++) {
        int n, m = 0;
        cin >> n;
        for (int i = 1; i <= n; i ++) {
            int s, e, l;
            cin >> s >> e >> l;
            stone[i] = {s, e, l};
            m += s;
        }
        
        sort(stone + 1, stone + 1 + n);
        memset(f, -0x3f, sizeof f);              //集合划分依据为恰好等于体积j的，所以需要赋值负无穷
        f[0] = 0;
        
        for (int i = 1; i <= n; i ++) {
            int s = stone[i].s, e = stone[i].e, l = stone[i].l;
            for (int j = m; j >= s; j --) {
                f[j] = max(f[j], f[j - s] + e - (j - s) * l);
            }
        }
        
        int res = 0;
        for (int i = 0; i <= m; i ++) res = max(res, f[i]);
        cout << "Case #" << H << ": " << res << endl;
    }
    
    return 0;
}

6. 多重背包问题 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 ++ ;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}