背包问题 ★★★★★★

参考：

详细：https://blog.csdn.net/na_beginning/article/details/62884939

九种背包问题，让你永恒拥有背包算法（贪心）：https://mp.csdn.net/postedit/89059758

01背包：https://blog.csdn.net/weixin_39059738/article/details/79924049

01背包：https://blog.csdn.net/mu399/article/details/7722810

LeetCode相关题目：

leetcode 322. Coin Change 完全背包问题【medium☆】

leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历

leetcode 279. Perfect Squares 类似背包问题 + 很简单的动态规划DP解决

leetcode 474. Ones and Zeroes若干0和1组成字符串最大数量+动态规划DP+背包问题

leetcode 518. Coin Change 2 类似背包问题，状态叠加【medium☆☆】

1. 初始化：

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。

• 有的题目要求“恰好装满背包”时的最优解，
• 有的题目则并没有要求必须把背包装满。

这两种问法的实现方法是在初始化的时候有所不同。

1） 要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。 

2） 如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。

如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。

如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

*** 这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。 

初始化情况一：

 LeetCode 322. Coin Change

完全背包问题，且要求正好装满（正好凑够amount钱）。需要求最小值，所以cnt初始化为 cnt = [float('inf') for j in range(amount+1)]

如果要求是最大值，则应初始化为cnt = [float('-inf') for j in range(amount+1)]

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount == 0:
            return 0
        if not coins:
            return -1
        cnt = [float('inf') for j in range(amount+1)]
        cnt[0] = 0
        for i in range(1,len(coins)+1):
            for j in range(amount+1):
                if j >= coins[i-1]:
                    cnt[j] = min(cnt[j],cnt[j-coins[i-1]]+1)
        return -1 if cnt[-1] > amount else cnt[-1]

 

2. 01背包问题：

问题描述：

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，每件物品数量只有一个，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

▶   01背包问题其实就可以化简为涂写下面的表格，其中每个数对应数组nArr中每个元素，初始化部分为0，然后从左上角按行求解，一直求解到右下角获取最终解nArr[5][12]。 

空间优化

　　空间优化，每一次f(i)(j)改变的值只与f(i-1)(x) {x:1...j}有关，f(i-1)(x)是前一次i循环保存下来的值；

　　因此，可以将f缩减成一维数组，从而达到优化空间的目的，状态转移方程转换为 B(j)= max{B(j), B(j-w(i))+v(i)}；

　　并且，状态转移方程，每一次推导V(i)(j)是通过V(i-1)(j-w(i))来推导的，所以一维数组中j的扫描顺序应该从大到小(capacity到0)，否者前一次循环保存下来的值将会被修改，从而造成错误。

 

练习题：

 https://www.cnblogs.com/Su-Blog/archive/2012/08/17/2644736.html

Problem Description

Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。

总结此题需要注意的三方面：

1. 第一：他可以拿到至少一份offer的最大概率p1。这句话需要转化为最小不收到offer的概率p2，p1=1-p2 ,这样就可以避免分类的情况。
2. 第二：最大背包因为状态转移变成了最小背包，注意变化。状态转移方程：dp[j]=min(dp[j],dp[j-a[i]]*(1.0–b[i]));
3. 第三：输入的最后有两个0。按题意是m!=0&&n!=0 ,而实际上n||m才能过。。

两种优化版的写法：

（1）

m = 10
v = [0.1,0.2,0.3]
w = [4,4,5]
p = [1 for j in range(m+1)]
for i in range(1,len(v)+1):
    for j in range(m,0,-1):
        if j >= w[i-1]:
            p[j] = min(p[j],p[j-w[i-1]]*(1-v[i-1]))
print(p)

 （2）

m = 10
v = [0.1,0.2,0.3]
w = [4,4,5]
p = [1 for j in range(m+1)]
for i in range(0,len(v)):
    for j in range(m,w[i],-1):
        p[j] = min(p[j],p[j-w[i]]*(1-v[i]))
print(p)

3. 完全背包问题：

问题描述：

有编号分别为a,b,c,d的四件物品，它们的重量分别是2,3,4,7，它们的价值分别是1,3,5,9，每件物品数量无限个，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

完全背包问题与01背包问题的区别在于每一件物品的数量都有无限个，而01背包每件物品数量只有一个。

▶ 价值矩阵的初始化不同：当只考虑一件物品a时，value[1][j] = j / weight[a]

▶ 递推公式计算时，value[i][y] = max{value[i-1][y], (value[i][y-weight[i]]+value[i])}

注意：这里当考虑放入一个物品 i 时应当考虑还可能继续放入 i，因此这里是value[i][y-weight[i]]+value[i], 而不是value[i-1][y-weight[i]]+value[i]。

name	weight	value	0	1	2	3	4	5	6	7	8	9	10
d	7	9	0	0	1	3	5	5	6	9	10	10	12
c	4	5	0	0	1	3	5	5	6	8	10	10	11
b	3	3	0	0	1	3	3	4	6	6	7	9	9
a	2	1	0	0	1	1	2	2	3	3	4	4	5

4. 多重背包问题

有编号分别为a,b,c的三件物品，它们的重量分别是1，2，2，它们的价值分别是6，10，20，他们的数目分别是10，5，2，现在给你个承重为 8 的背包，如何让背包里装入的物品具有最大的价值总和？ 

多重背包和01背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。

方法一：

作为一个新问题考虑，由于每个物品多了数目限制，因此初始化和递推公式都需要更改一下。

▶ 初始化时，只考虑一件物品a时，value[1][j] = v[1] * min{num[1], j/weight[1]}。

▶ 计算考虑i件物品承重限制为y时最大价值value[i][j]时，递推公式考虑两种情况，要么第 i 件物品一件也不放，就是value[i-1][j], 要么第 i 件物品放 k 件，其中 1 <= k <= (j/weight[i])，考虑这一共 k+1 种情况取其中的最大价值即为value[i][j]的值，即

                      value[i][j] = max{value[i-1][j], (value[i-1][j-k*weight[i]]+k*value[i])}。

这里为什么不能像完全背包一样直接考虑f[i][j-weight[i]]+value[i]呢？因为这样不容易判断第 i 件物品的个数是否超过限制数量 num[i]。

name	weight	value	num	0	1	2	3	4	5	6	7	8
c	2	20	2	0	6	20	26	40	46	52	58	64
b	2	10	5	0	6	12	18	24	30	36	42	48
a	1	6	10	0	6	12	18	24	30	36	42	48

 方法二：

由01背包的分析可知，01背包中允许放入的物品有重复，即01背包中如果考虑要放入的物品的重量和价格相同，不影响最终的结果，因为我们可以考虑把多重背包问题中限制数目的物品拆分成单独的一件件物品，作为01背包问题考虑。问题解法和01背包一致，这里不再列举出动态规划的表格了。