0%

机试——背包问题（动态规划）

发表于 更新于 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

​ 背包问题是指给定义一些候选集，在这些候选集中找出一些特定要求的组合，组合出目标值(也就是用一些大小不同的东西装满背包)。

​ 常见的背包问题问题有：能否组成一个值，组成一个值得最小元素个数，组成一个值可使用的最多元素个数等

​ 背包问题根据背包选用的物品是否可以复用，分为完全背包问题和0/1背包问题。根据背包的维度可以分为一维背包问题和二维背包问题。下面我们针对这些问题中的关键点进行总结：

0/1背包问题：

​ 1.遍历时一定要从后向前遍历目标值数组（dp），不能从前向后，从前往后会产生一个物品适用多次的问题

​ 2.要在最外层循环遍历物品，这样能保证在选择将物品是否使用在哪里使用

​ 3.dp数组长度为目标值得大小+1

完全背包问题：

​ 1.dp数组长度为目标值得大小+1

​

一点想法

对于从后到前的遍历动态规划每隔一段时间再看多会很难理解，这也是动态规划经常做的不是太好的原因吧，因此把从后向前整个流程梳理一下。

一维背包问题

1.零钱兑换(leetcode 232)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

1
2
3
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

1
2
输入: coins = [2], amount = 3
输出: -1

说明:
你可以认为每种硬币的数量是无限的。

分析:这道题题目是标准的完全背包问题，用数目不定的元素组合成指定金额，因为各个值都可能有两种情况组成：1.直接由当前金额的硬币直接组成 2.由之前组成的金额再加上一个硬币组成，因此递推关系为:

​ dp[i] = min(dp[i],dp[i-c]) c为硬币的各个金额

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def coinChange(self, coins: List[int], amount: int) -> int:
       MAX_INT = pow(2,32)-1
       
       dp = [MAX_INT for _ in range(amount+1)]
       dp[0] = 0
       
       for i in range(1,len(dp)):
           for c in coins:
               if i-c>=0:
                   dp[i] = min(dp[i],dp[i-c]+1)

       if dp[-1]==MAX_INT:
           return -1
       else:
           return dp[-1]

2.小米大礼包

小米之家是成人糖果店。里面有很多便宜，好用，好玩的产品。中秋节快到了，小米之家想给米粉们准备一些固定金额大礼包。对于给定的一个金额，需要判断能不能用不同种产品（一种产品在礼包最多出现一次）组合出来这个金额。聪明的你来帮帮米家的小伙伴吧。

输入描述:
1
2
3
输入 N （N 是正整数， N  <= 200）
输入 N 个价格p（正整数, p <= 10000）用单空格分割
输入金额 M（M是正整数，M <= 100000 ）
输出描述:
1
2
能组合出来输出 1
否则输出 0

示例1

输入：

1
2
3
6
99 199 1999 10000 39 1499
10238

输出：

1
1

分析：这是一个标准的一维0/1背包问题，最终目标看是否能完成组合。因此首先我们推断出递推公式

​ dp[i] = max(dp[i],dp[i-c])

注意：0/1背包问题必须要从后往前进行遍历，否则会出现已经当前c在前面使用dp[i] = max(dp[i],dp[i-c])已经更新过的结果，相当于使用了多次c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())

nums = list(map(int,input().split()))

target = int(input())

dp = [0 for i in range(target+1)]


dp[0] = 1

for c in nums:
    for i in range(target,c-1,-1):
        dp[i] = max(dp[i],dp[i-c])

print(dp[-1])

二维背包问题

1.一和零(leetcode 474)

在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:

  1. 给定 0 和 1 的数量都不会超过 100。
  2. 给定字符串数组的长度不会超过 600。

示例 1:

1
2
3
4
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4

解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。

示例 2:

1
2
3
4
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2

解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。

分析：这一题是比较典型的0/1背包问题,将翻译后的string看做一个物品，这个物品有两个value，value1为0

的个数，value2为1的个数，初始状态下你有用m个0和n个1，求最多能获取的物品总个数。

​ 核心依然是找到状态转移方程，因为题目具有两个变量，属于二维背包问题，因此创建一个二位数组，分别代表使用num0个0和num1个1时可以获得的最多字符串数。

​ dp[num0][num1] =max(dp[num0][num1],dp[nums0-zeros][nums1-ones]+1)

注意：这里的二重循环必须从m,n开始递减，而不能从0开始递增，因为在0/1背包问题中，每个物品只能被使用一次，如果从0开始向后，dp[num0][num1]可以获得的是这次循环中更新过的dp[num0][num1] =max(dp[num0][num1],dp[nums0-zeros][nums1-ones]+1)，相当于一个物品可以重复购买，变成了完全背包问题。

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
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        
        tmp = []
        for i in strs:
            zeros = 0
            ones = 0
            
            for j in i:
                if j=='0':
                    zeros+=1
                else:
                    ones+=1
            tmp.append([zeros,ones])
            
        #m 行，代表0  n列代表1
        dp = [[0 for _ in range(n+1)]for _ in range(m+1)]
        
        for s in tmp:
            zeros = s[0]
            ones = s[1]
            for nums1 in range(m,zeros-1,-1):
                for nums2 in range(n,ones-1,-1):
                    dp[nums1][nums2] = max(dp[nums1][nums2],dp[nums1-zeros][nums2-ones]+1)

        return dp[-1][-1]

2.大礼包

在LeetCode商店中， 有许多在售的物品。

然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。

每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。

任意大礼包可无限次购买。

示例 1:

1
2
3
4
5
6
7
输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释: 
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。

最小车票花费