背包问题 4

1021 货币系统

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案

完全背包, 裸题

#include <iostream>

using namespace std;

typedef long long LL;

const int M = 3010;

int n, m;
LL f[M];

int main()
{
    cin >> n >> m;

    f[0] = 1; // 一个物品都不选, 也是一种方案
    for (int i = 0; i < n; i ++ )
    {
        int v;
        cin >> v;
        for (int j = v; j <= m; j ++ )
            f[j] += f[j - v];
    }

    cout << f[m] << endl;

    return 0;
}

532 加强版货币系统

数学原理: 极大线性无关组

等价: 判断 a[i] 能不能用 a[1] ~ a[i-1] 线性表出

完全背包

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

using namespace std;

//这题是一道线性代数问题
//求解一个向量组的秩(最大无关向量组的向量个数)
//但是代码写起来就是一个模拟筛的过程

//从小到大，先查看当前数有没有被晒掉:
//1)如果没有就把它加入到最大无关向量组中，并把他以及他和此前的硬币的线性组合都筛掉
//2)如果有就不理会
//即就是在完全背包求方案数的过程中，统计那些初始没有方案数的物品
//这样就变成一个完全背包问题了

const int N = 110, M = 25010;
int n;
int v[N];
bool f[M];

int main()
{
    int T = 1;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 1; i <= n; ++ i) cin >> v[i];
        /*
        对于一个 无效的 元素 ai
        他只会被 小于 他的元素的 线性组合 表出，满足该要求的 ai 就要被 筛掉
        所以我们要先 排序, 相当于是 "剪枝"
        */
        sort(v + 1, v + n + 1);

        //我们只需统计所有物品的体积是否能被其他的线性表出
        //因此背包的体积只需设置为最大的物品体积即可
        //res用来记录最大无关向量组的个数
        int m = v[n], res = 0;
        memset(f, 0, sizeof f);
        f[0] = true;    //状态的初值
        for (int i = 1; i <= n; ++ i)
        {
            //如果当前物品体积被之前的物品组合线性筛掉了，则它是无效的
            if (f[v[i]]) continue;
            //如果没有被筛掉，则把它加入最大无关向量组
            res ++ ;
            //筛掉当前最大无关向量组能线性表示的体积
            for (int j = v[i]; j <= m; ++ j)
            {
                f[j] |= f[j - v[i]];
            }
        }
        //输出最大无关向量组的向量个数
        cout << res << endl;
    }
    return 0;
}

7 混合背包问题

动态规划

• 状态表示
  • 集合: 只从前i件物品中选，且体积不超过j的选法
  • 属性: max
• 状态计算
  • 01: f[i, j] = max ( f[i-1,j], f[i-1,j-v[i]]+w[i] )
  • 完全: f[i, j] = max ( f[i-1, j], f[i-1, j-v[i]]+w[i] ). by 递推
  • 多重: f[i, j] = max ( f[i-1, j], f[i-1, j-v[i]]+w[i], f[i-1, j-2v[i]] + 2w[i], ...)

题面:

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

物品一共有三类：

• 第一类物品只能用1次（01背包）
• 第二类物品可以用无限次（完全背包）
• 第三类物品最多只能用 si 次（多重背包）

每种体积是 vi，价值是 wi

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

输入格式:

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量

• si=−1 表示第 i 种物品只能用1次
• si=0 表示第 i 种物品可以用无限次
• si>0 表示第 i 种物品可以使用 si 次

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N], s[N];
int f[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)
    {
        //完全背包
        if (!s[i])
        {
            for (int j = v[i]; j <= m; ++ j)
            {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        }
        else
        {
            //把多重背包用二进制优化
            //这样就变成做多个01背包了
            if (s[i] == -1) s[i] = 1;
            //二进制优化
            for (int k = 1; k <= s[i]; k *= 2)
            {
                for (int j = m; j >= k * v[i]; -- j)
                {
                    f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
                }
                s[i] -= k;
            }
            if (s[i])
            {
                for (int j = m; j >= s[i] * v[i]; -- j)
                {
                    f[j] = max(f[j], f[j - s[i] * v[i]] + s[i] * w[i]);
                }
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

11 背包问题求方案数

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

输出 最优选法的方案数。注意答案可能很大，请输出答案模 1e9+7 的结果

1. 01背包 f[i, j]
   1. 定义: 前 \(i\) 个物品，占容量 恰好 为 \(j\) 的选法
   2. 状态转移: f[i, j] = max ( f[i-1, j], f[i-1, j-v[i]]+w[i] )
2. g[i,j]: f[i,j] 取最大值时的方案数
   1. 左大: g[i,j] = g[i-1,j]
   2. 右大: g[i,j] = g[i-1,j-v[i]]
   3. 相等: g[i,j] = g[i-1,j] + g[i-1,j-v[i]]
   4. 

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n, m;
int f[N], g[N];

int main()
{
    cin >> n >> m;

    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    g[0] = 1;

    for (int i = 0; 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 s = 0;
            if (f[j] == maxv) s = g[j];
            if (f[j - v] + w == maxv) s = (s + g[j - v]) % mod;
            f[j] = maxv, g[j] = s;
        }
    }

    int res = 0;
    for (int i = 1; i <= m; i ++ )
        if (f[i] > f[res])
            res = i;

    int sum = 0;
    for (int i = 0; i <= m; i ++ )
        if (f[i] == f[res])
            sum = (sum + g[i]) % mod;

    cout << sum << endl;

    return 0;
}

734 能量石

贪心 + dp

• 吃哪些？
• 这些按照什么顺序吃？

fix: 总体积恰好是j

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

int n;
struct Stone
{
    int s, e, l;
}stones[N];

bool cmp(Stone a, Stone b)
{
    // 回调函数, 用来sort自定义方式
    return a.s * b.l < b.s * a.l;
}

int f[N][M];

int main()
{
    int T;
    cin >> T;
    for (int C = 1; C <= T; C ++ )
    {
        cin >> n;
        int m = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int s, e, l;
            cin >> s >> e >> l;
            stones[i] = {s, e, l};
            m += s;
        }

        sort(stones + 1, stones + 1 + n, cmp);

        for (int i = 1; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j];
                if (j >= stones[i].s)
                {
                    int s = stones[i].s, e = stones[i].e, l = stones[i].l;
                    f[i][j] = max(f[i][j], f[i - 1][j - s] + max(0, e - l * (j - s)));
                }
            }

        int res = 0;
        for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i]);

        printf("Case #%d: %d\n", C, res);
    }

    return 0;
}