以下摘要由GPT-4o生成:
本文讨论了动态规划（DP）中最基本的背包问题，主要包括01背包、完全背包、多重背包和二维费用背包的特点及求解方法。首先，01背包问题需要在有限的容量内选择物品以最大化价值，通过定义状态f[i][v]来表示前i件物品在容量为v的情况下的最大价值，并进行空间优化至一维数组。完全背包则允许每种物品取无限次，涉及到正序遍历的处理方式。多重背包则通过二进制拆分将其转化为01背包问题，以便于求解。最后，二维费用背包问题结合两种代价，通过状态f[i][v][u]来计算在给定体积和重量限制下的最大价值。这些背包问题的核心在于巧妙的构造子问题和状态转移方程。

1.最典型，最基本的dp问题

2.背包的每个容量就是“状态”

  • 01背包(最基础的背包问题):
  • 有N件物品和一个容量为V的背包。第I件物品的费用是c[i]，价值是w[i]。
  • 求解将哪些物品装入背包可使价值总和最大。
  • 问题特点:每种物品仅有一件，可以选择放或不放;
  • 思考:在每个物品都有可能被选中的前提下，如何构造“子问题”?
  • 无序变有序的方法:依次考虑前1、前2、前3…前i个物品;
  • 状态定义:f[i][v]表示前i件物品放入一个容量为v的背包可以获得的最大价值。

3.0-1背包问题优化

  • 1背包问题伪代码如下:
1
2
3
4
5
6
for i = 1 to n            //所有物品;

for j = V  to v[i]     //思考:为何没必要循环到0?

dp[j] = max(dp[j - v[i]] + w[i],dp[j]);

-

  • 空间成功优化到一维V。因为j小于v[i]时已经不满足条件。

  • 整个代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int dp[1001], w[1000],c[1000];
int main()
int num,n, V, i j;
scanf("%d",&num);
while(num--){
	scanf("%d %d", &n, &V) //输入物品n个，背包容量为V
    for (i=0; i<n; i++) scanf("%d",&w[i]); //输入物品价值
	for (i=0; i<n; i++) scanf("%d",&c[i]); //输入物品体积
	memset(dp, 0, sizeof(dp));//dp数组初始化
	for (i=0; i<n; i++ )
	for(j=V; j>=c[i]; j--)
	dp[j] = max(dp[j], dp[j-c[i]] + w[i]);
	printf("%d\n", dp[V]);
}

优化后的代码是按逆序遍历数组，可以避免同一物品被拿多次。

4.完全背包

  • 完全背包特点:一种物品可以取无数个

  • 可否转化成01背包问题?

  • 朴素的转化方式是?

  • 回忆01背包为何要对容量按照逆序循环?

  • 和01背包类似,不过就是正着写（因为正着写可能会有同个物品重复拿取的情况，而完全背包符合这种特点）

  • 深度思考:这类能不能达到的问题应该怎么实现?

5.多重背包

  • 多重背包特点:
    一种物品有C个，既不是固定的1，也不是无数个，是可以被分的

  • 优化的方法:

    核心思想

    将每类物品的数量 C 拆分成若干组，每组包含 1, 2, 4, ..., 2^{k-1}, C - (2^k - 1) 个物品，通过这些组的组合可表示 1~C 之间的任意数量。这样将多重背包转化为 log(C) 个物品的01背包问题，时间复杂度从 O(N*V* C) 降至 O(N*V* logC)

  • 运用二进制，进行物品拆分,转化成01背包
    比如:13余相同的物品可分成4组(1,2,4,6)
    用这4组可以组成任意一个1~13之间的数!
    原理:一个数总可以用2^k表示

  • 然后进行01背包

  • 优化部分的参考代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
      int cnt = 0; // 拆分后的物品总数
      int x = C;    // *当前剩余数量*
      int t = 1;    // 当前二进制基数
      
      while (t <= x) {
          v[cnt] = a * t;   // 体积为原体积乘以数量t
          c[cnt] = b * t;   // 价值为原价值乘以数量t
          cnt++;
          x -= t;           // 剩余数量减少t
          t <<= 1;          // 基数翻倍（等效于 t *= 2）
      }
      
      // 处理剩余不足t的部分
      if (x > 0) {
          v[cnt] = a * x;
          c[cnt] = b * x;
          cnt++;
      }
    - ***01背包部分***

    ```c++
    int dp[N]; // dp[j] 表示容量j时的最大价值

    // 初始化dp数组
    memset(dp, 0, sizeof(dp));

    // 遍历所有拆分后的物品
    for (int i = 0; i < cnt; i++) {
        // 逆序遍历容量（01背包特性）
        for (int j = V; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
        }
    }

6.二维费用背包

二维费用背包问题
对于每件物品，具有两种不同的费用，选择这件物品必须同时付
出这两种代价;对于每种代价都有一个可付出的最大值(比如，
背包容量、最大承重)，求怎样选择物品可以得到最大的价值。
设第i件物品所需的两种代价分别为a[i]和b[i]，两种代价可付
出的最大值(比如体积和重量)分别为V和U，物品的价值为w[i]。
对应算法:费用加了一维，只需状态也加一维即可!
设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的
最大价值，状态转移方程则为:

  • f[i][v][u]=max( f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i])