背包问题 1

背包问题 树图

背包问题 Review

• 状态表示: f[i, j] (一般是2维)
  • 集合: 所有 只从前i个物品中选，且总体积不超过j 的选法的集合
  • 属性: Max
• 状态计算
  • f[i, j] <--- ...
  • 划分依据: 用 “最后一步” 来划分
• 01背包:
  • 定义: 每个物品，选 or 不选
  • 
• 完全背包:
  • 定义: 每个物品，选 0 1 2 3 4 ... 个 （无限, 这里的S是体积边界对应的个数, 每个取法的S都一样）
  • 推理:
  • 优化(数学):
  • final: f[i, j] = max (f[i-1, j], f[i, j-v] + w)
• 多重背包:
  • 定义: 每个物品，选 0 1 2 3 ... \(S_i\) 个
  • 滑动窗口推导思路:

注意⚠️: 当空间优化成1维后, 只有 完全背包问题 的体积是 从小到大 扫描的

// 背包模板
for 物品:
    for 体积:
        for 决策:

多重背包

6 多重背包问题III

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

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

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

#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;
}

这题太难了，不用写

01背包

知识图谱:

423 采药

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> m >> n;
    // 0-1 背包 纯模板
    for (int i=0; i<n; i++)
    {
        int v, w;
        cin >> w >> v;

        for (int j=m; j>=w; j--) f[j] = max(f[j], f[j-w] + v);
    }

    cout << f[m] << endl;

    return 0;
}

1024 装箱问题

本质: 价值(w) 也是 体积(v)

#include <iostream>
#include <algorithm>

using namespace std;

const int M = 20010;

int n, m;
int f[M];

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ )
    {
        int v;
        cin >> v;
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + v);
    }

    cout << m - f[m] << endl;

    return 0;
}

1022 宠物小精灵之收服

二维费用 (下节课) + 及其优化

体积:

• 精灵球数量
• 皮卡丘体力值

价值:

• 小精灵的数量

动态规划:

• 状态表示: f[i,j,k]
  • 所有只从 前i个物品中选，且花费1不超过j，花费2不超过k的选法 的最大价值
• 状态计算:
  • f[i, j, k] = max( f[i-1, j, k] , f[i-1, j-v1[i], k-v2[i]] + 1)

求解:

1. 最多收服的小精灵数量: f [K, N, M]
2. 最少消耗体力: f[K, N, m] == f[K, N, M]

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 510;

int n, V1, V2;
int f[N][M];

int main()
{
    // 精灵球总数 皮卡丘初始体力值 小精灵总数
    cin >> V1 >> V2 >> n;
    for (int i = 0; i < n; i ++ )
    {
        int v1, v2;
        cin >> v1 >> v2; // 需要的精灵球数 伤皮卡丘的体力值
        for (int j = V1; j >= v1; j -- ) // 精灵球
            for (int k = V2 - 1; k >= v2; k -- ) // 体力值
                // 从V2-1开始而不是V2, 因为皮卡丘的体力值不能为0
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
    }

    // (1) 最多收服的小精灵数量
    cout << f[V1][V2 - 1] << ' ';

    // (2) 求剩余体力值max <=> 消耗体力值min
    int k = V2 - 1;
    while (k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k -- ;
    cout << V2 - k << endl;

    return 0;
}

这里 (2) 的思路比较令人费解:

本质上是: 找到满足最大价值的所有状态里，第二维费用消耗最少的

换一种写法:

// (2) 求剩余体力值max <=> 消耗体力值min
int cost_health = V2 - 1;
for (int k = 0; k <= V2-1; k++)
{
    if (f[V1][k] == f[V1][V2-1])
    {
        cost_health = min(cost_health, k);
    }
}
cout << V2 - cost_health << endl;