总结总结数据结构和算法不会的题目

发表于 更新于 分类于
失败不是什么丢人的事情，从失败中全无收获才是。

经典题目的解题思路和不会的题目总结一下。

背包问题

背包问题，看的是《背包问题九讲》，PDF下载，在线看背包问题九讲，bilibili ACWing讲解视频。

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

01背包问题

每种物品仅有一件，可以选择放或不放。

伪代码如下：

1
2
3
4
F[0, 0...V] = 0
for i = 1 to N:
	for v = Ci to V:
		F[i,v] = max(F[i-1,V], F[i-1,v-Ci] + Wi)

时间复杂度O(VN)不能再降了，但是空间复杂度可以优化到O(V)。首先，i只与i-1相关，那就可以降到O(2V)；其次，在每次主循环中我们以v=V…Ci的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态F[i-1,v-Ci] 的值。

伪代码如下：

1
2
3
4
F[0...V] = 0
for i = 1 to N:
	for v = V to Ci:
		F[v] = max(F[V], F[v-Ci] + Wi)

可以把01背包抽象出处理过程，

1
2
3
4
5
6
7
8
9
# C和W表示一件物品的花费和价值
def ZeroOnePack(F, C, W)
	for v = V to C:
		F[v] = max(F[V], F[v-C] + W)

# 01背包问题可以写成
F[0...V] = 0
for i = 1 to N:
    ZeroOnePack(F, Ci, Wi)

初始化细节：

  • 如果要背包恰好装满，则除了F[0]=0， 其他均初始化为-∞，可以保证最终F[V]是恰好装满的最优解
  • 如果只是要价值最大，则都初始化为0

完全背包问题

每种物品有无限件可以用。

思路一：将多个物品拆成单个物品来用。可以做优化，将花费大于V的先删选出去。

思路二：将第i种物品拆成费用为$c[i]*2^k$，价值为$w[i]*2^k$的若干物品，当然$k$只需要取遍$c[i]*2^k<=V$即可，因为二进制思想，任意数目都可以由二进制数目来组合。

伪代码：

1
2
3
4
F[0...V] = 0
for i = 1 to N:
	for v = Ci to V:	# 注意此处是从Ci到V,因为多件物品时，可以考虑出现Ci的情况
		F[v] = max(F[V], F[v-Ci] + Wi)

完全背包可以抽象为

1
2
3
4
5
6
7
8
9
# C和W表示一件物品的花费和价值
def CompletePack(F, C, W)
	for v = C to V:
		F[v] = max(F[V], F[v-C] + W)

# 完全背包问题可以写成
F[0...V] = 0
for i = 1 to N:
	CompletePack(F, Ci, Wi)

多重背包问题

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

可以转换成01背包问题和完全背包问题。

1
2
3
4
5
6
7
8
9
10
def MultiplePack(F, cost, weight, amount):
    if(cost*amount >= V)	# 视作无限数目
    	CompletePack(F, cost, weight)
        return
    int k=1
    while k<amount: # 拆分成01背包
        ZeroOnePack(F, k*Ci, k*Wi)
        amount = amount-k
        k = k*2
     ZeroOnePack(F, amount*cost, amount*weight)	# 拆封成剩下的个数

混合三种背包问题

就是分类别进行处理。

1
2
3
4
5
6
7
for i = 1 to N:
	if 属于01背包问题:
		ZeroOnePack(F, Ci, Wi)
	else if 属于 完全背包问题:
		CompletePack(F, Ci, Wi)
    else if 属于多重背包问题:
        MultiplePack(F, Ci,Wi, Ni)

二维费用的背包问题

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。

设这两种代价分别为代价1和代价2，第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-Ci, u-Di] + Wi)

按照01背包的优化，可以使用二维数组：当每件物品只可以取一次时，对变量u和v采用逆序循环，当物品有如完全背包问题时采用顺序循环，当物品有如多重背包问题时，就拆分处理。

分组的背包问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：

1
f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}

觉得就跟01背包问题很像，只不过这里一组可以看成一个物体

使用一维数组的伪代码：

1
2
3
4
for k = 1 to K:
	for v = V to 0:
		for all item i in group k:
        	F[v] = max(F[v], F[v-Ci] + Wi)

这样三层循环能够保证每一组内的物品最多只有一个会被添加到背包中。

后面的：有依赖背包问题、泛化物品就不看了，应该笔试面试考不到那里去吧，考到了我再来学