背包问题本质: 将"代价"变成二维的（重量+体积）

动态规划:

# 8 二维费用的背包问题

二维费用 + 01/完全/多重/分组 背包

本质: 将“代价”变成二维的（重量+体积）

动态规划:

![[image-20250812131030120.p- 状态计算: - f[i, j] = f[i-1, j] + f[i-1, j-k*vi] (k=1, 2, 3, ...) - 由于是完全背包，所以可以进行"递推优化" - - final: f[i, j] = f[i-1, j] + f[i, j-v]0]]

#include <iostream>

using namespace std;

const int N = 110;

int n, V, M;
int f[N][N];

int main()
{
    cin >> n >> V >> M;

    for (int i = 0; i < n; i ++ ) // 物品
    {
        int v, m, w;
        cin >> v >> m >> w;
        for (int j = V; j >= v; j -- ) // 体积
            for (int k = M; k >= m; k -- ) // 重量
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    }

    cout << f[V][M] << endl;

    return 0;
}

一般来说，有几个“变量” 就 有几个 for

278 数字组合

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案:

方案数 很简单，就是求解属性变成count了

思路:

• M: 背包容量
• 把每个数看成一个物品，\(A_i\) 看成是体积
• 目标: 求出总体积恰好是M的方案数

动态规划

• 状态表示: f[i, j]
  • 集合: 所有只从前 i 个物品中选，且总体积恰好为 j 的方案的集合
  • 属性: count
• 状态计算:
  • f[i, j] = f[i-1, j] + f[i-1, j-Ai]
  • 

// 朴素 二维
#include<iostream>
using namespace std;

const int maxn = 1e4+10;

int a[maxn];
int f[maxn][maxn];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin >> a[i];

    // 初始化: 什么都不选 -> 恒为0 -> 也是一种策略
    for (int i=0; i<=n; i++) f[i][0] = 1;

    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            f[i][j] = f[i-1][j];
            if (j >= a[i]) // 因为是从i-1转移而来, 因此1D优化时, j从大到小
                f[i][j] = f[i][j] + f[i-1][j-a[i]];
        }
    }

    cout << f[n][m] <<endl;
    return 0;
}

// 一维 优化
#include<iostream>
using namespace std;

const int maxn = 1e4+10;

int a[maxn];
int f[maxn];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin >> a[i];

    // 初始化: 什么都不选 -> 恒为0 -> 也是一种策略
    for (int i=0; i<=n; i++) f[0] = 1;

    for (int i=1; i<=n; i++)
    {
        for (int j=m; j>=a[i]; j--)
        {
            f[j] = f[j] + f[j-a[i]];
        }
    }

    cout << f[m] <<endl;
    return 0;
}

1019 庆功会

多重背包

暴力版复杂度: n x m x s = \(3 \times 10^7\). Ok!!!

#include<bits/stdc++.h>

using namespace std;

const int N = 6010;

int n, m;
int f[N]; // 动态规划

int main()
{
    cin >> n >> m; // m: 金额上限

    for (int i=0; i<n; i++) // 物品
    {
        int v, w, s;
        cin >> v >> w >> s;

        for (int j=m; j>=0; j--) // 金额
        {
            for (int k=0; k<=s && k*v<=j; k++) // 当前物品选多少件
            {
                // 注意: k<=s && k*v <= j
                f[j] = max(f[j], f[j-k*v] + k*w);
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

1023 买书

完全背包

动态规划

• 状态表示: f[i, j]
  • 集合: 所有只从前 i 类物品中选，且总体积恰好为 j 的方案的集合
  • 属性: count
• 状态计算:
  • f[i, j] = f[i-1, j] + f[i-1, j-k*vi] (k=1, 2, 3, ...)
  • 由于是完全背包，所以可以进行“递推优化”
  • 
  • final: f[i, j] = f[i-1, j] + f[i, j-v]

// 二维朴素版
#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[5] = {0, 10, 20, 50, 100};
int f[5][N];
int n;

int main()
{
    cin >> n;

    f[0][0] = 1; // 这也是一种解, 初始化
    for (int i=1; i<=4; i++)
    {
        for (int j=0; j<=n; j++)
        {
            f[i][j] = f[i-1][j];
            if (j >= a[i]) f[i][j] += f[i][j-a[i]];
        }
    }

    cout << f[4][n] << endl;
    return 0;
}

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

// 一维优化版

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int v[4] = {10, 20, 50, 100};
int f[N];

int main()
{
    cin >> n;

    f[0] = 1;
    for (int i = 0; i < 4; i ++ )
        for (int j = v[i]; j <= n; j ++ )
            f[j] += f[j - v[i]];

    cout << f[n] << endl;

    return 0;
}

转移原则: 从i-1层转移而来，就要从大到小循环；从i层转移而来，要从小到大循环