zzoce 🧊
背包问题

背包问题

Thu Oct 03 2024
zzcoe
9 分钟
数据结构与算法 动态规划 单调队列
1553 字

01 背包#

竞赛中心 - 蓝桥云课 (lanqiao.cn)题意概要：有 nn 个物品和一个容量为 WW 的背包，每个物品有重量 wiw_i 和价值 viv_i 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

CPP
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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
struct node {
    int w,v;
};
node mp[110];
int dp[1100];
int main ()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>mp[i].w>>mp[i].v;
    }
    for (int i=1;i<=n;i++){
    //从大向下遍历，如果从小向大遍历，dp[x]会对dp[y]产生影响，x<y
    //例如在dp[x]已经放过物品i，在dp[y]处又放了一次，相当于物品i不限量，可以无限取
        for (int j=m;j>=mp[i].w;j--){
            dp[j]=max(dp[j],dp[j-mp[i].w]+mp[i].v);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

完全背包#

2.小明的背包2 - 蓝桥云课 (lanqiao.cn)完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

CPP
1
2
3
4
5
6
    for (int i=1;i<=n;i++){
     //例如在dp[x]已经放过物品i，在dp[y]处又放了一次，相当于物品i不限量，可以无限取
        for (int j=mp[i].w;j<=m;j++){
            dp[j]=max(dp[j],dp[j-mp[i].w]+mp[i].v);
        }
    }

多重背包#

3.小明的背包3 - 蓝桥云课 (lanqiao.cn)多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 kik_i 个，而非一个。

一个很朴素的想法就是：把「每种物品选 kik_i 次」等价转换为「有 kik_i 个相同的物品，每个物品选一次」。这样就转换成了一个 0-1 背包模型，套用上文所述的方法就可已解决。

CPP
1
2
3
4
5
6
7
8
9
10
11
12
    for (int i=1;i<=n;i++){
        for (int j=m;j>=mp[i].w;j--){
            for (int l=1;l<=mp[i].k;l++){
                if (j>=l*mp[i].w){
                    dp[j]=max(dp[j],dp[j-mp[i].w*l]+l*mp[i].v);
                }else {
                    break;
                }
            }

        }
    }

但此时会发现再取物品 i 时每次增加一个是非常浪费时间的，时间复杂度是 O (NVK)。这时可以采用 二进制分组优化 使得时间复杂度将为 O (NVlogK)。

二进制分组优化#

具体地说就是将物品 i 的数量 k 按照二进制的方式拆分，最后不足拆分的另算一个，举几个例子 6=1+2+3 8=1+2+4+1 18=1+2+4+8+3 31=1+2+4+8+16 这样每种物品都可以分成几个，质量和价值都不相同的物品，在使用 01 背包的方式解决，二进制分组代码如下

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Index = 0;
For (int i = 1; i <= m; i++) {
  Int c = 1, p, h, k;//分别是价值，重量，个数
  Cin >> p >> h >> k;
  While (k > c) {
    K -= c;
    List[++index]. W = c * p;
    List[index]. V = c * h;
    C *= 2;
  }
  If (k!=0){
	  List[++index]. W = p * k;
	  List[index]. V = h * k;
  }
}

单调队列优化#

时间复杂度 O (NV)，与 01 背包相同 思路：假如由一个物品的质量是w，价格是m。那么在背包质量为v时f[v]的最大值一定是从f[v-w], f[v-2*w]... F[v-k*w]当中的某个加上相应的能增加的价值得来的，其中 k 是该物品的个数。那么我们就可以使用单调队列优化这样的一个分组，维护改组的最大值。以此降低时间复杂度 注意：

  • 不是维护组中的f[v-i*w]最大，而是f[v-i*w]+i*m最大
  • 在 DP 的过程中需要不断地对f[v]进行修改，但又要维护f的最值，随意我们另开一个数组来备份f数组，用来单调队列优化

代码：

CPP
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
For (int i=1; i<=n; i++){
		Memcpy (df, f, sizeof (f));//将 f 备份
		Cin>>w>>m>>k;//质量，价值，数量
		For (int j=0; j<w; j++){//分成 w 个组, 第一次放入物品的状态
			deque<int> dq;//队列存放的是背包当前的质量
			For (int l=j; l<=v; l+=w){//对每个组使用单调队列
				While (! Dq.Empty ()&&df[l]>=df[dq.Back ()]+(l-dq.Back ())/w*m){
					//当前值，比队尾存放的状态加上能新增的所有价值后
					//还要大，则队尾出队，维护最大值
					Dq. Pop_back ();
				}
				//新的优解，也就是价值更高入队
				Dq. Push_back (l);
				If (! Dq.Empty ()&&dq.Front ()<l-k*w){
					//过期元素出队
					//队列头不在窗口[l-k*w, l-w]内，
					//也就是 l 不会是从这个质量状态过来的
					Dq. Pop_front ();
				}
				If (! Dq.Empty ()){
					//更新背包价值
					F[l]=max (df[l], df[dq.Front ()]+(l-dq.Front ())/w*m);
				}
			}
		}
}

二维费用背包#

这道题是很明显的 0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间），只需在状态中增加一维存放第二种价值即可。

P1855 榨取kkksc03 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CPP
1
2
3
4
For (int k = 1; k <= n; k++)
  For (int i = m; i >= mi; i--)    // 对经费进行一层枚举
    For (int j = t; j >= ti; j--)  // 对时间进行一层枚举
      Dp[i][j] = max (dp[i][j], dp[i - mi][j - ti] + 1);

分组背包#

方法一#

这种题怎么想呢？其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

再说一说如何进行存储。我们可以将t[k][i] 表示第 k 组的第i件物品的编号是多少，再用cnt[k]表示第k组物品有多少个。

P1757 通天之分组背包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CPP
1
2
3
4
5
For (int k = 1; k <= ts; k++)          // 循环每一组
  For (int i = m; i >= 0; i--)         // 循环背包容量
    For (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      If (i >= w[t[k][j]])             // 背包容量充足
        Dp[i] = max (dp[i], dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像 0-1 背包一样状态转移

方法二#

CPP
1
2
3
4
5
6
7
8
9
10
11
For (int i=0; i<k; i++){//循环物品
        For (int j=N; j>=m[i]. A; j--){//循环背包
            If (dp[j-m[i]. A]. J[m[i]. C]!=1){//如果这一组没放过
                For (int k=0; k<=100; k++){
                    Dp[j]. J[k]=dp[j-m[i]. A]. J[k];
                }
                Dp[j]. J[m[i]. C]=1;
                Dp[j]. Sum=max (dp[j]. Sum, dp[j-m[i]. A]. Sum+m[i]. B);
            }
        }
    }