本文共 4079 字,大约阅读时间需要 13 分钟。
@Author:Runsen
@Date:2020/9/15
动态规划需要搞定三个系列:三个背包,零钱问题和股票问题。今天就开始干掉三个背包问题。
三个背包问题:01背包,多重背包,完全背包。上次搞定了01背包,那么继续学习完全背包。
我们有 N N N种物品,物品 i i i的重量为 w [ i ] w[i] w[i],价格为 p [ i ] p[i] p[i]。我们假定所有物品的重量和价格都是非负的,背包所能承受的最大重量W,每种物品都有无限件可用,则该问题成为完全背包问题 。
题目来源:https://www.acwing.com/problem/content/description/3/
先上代码,和01背包问题的解法有略微的改动,区别在于遍历体积 j j j时从逆序改为顺序,就只有这一个不同,在上一篇博客中有关于01背包问题的理解。
# 代码基本一样n, v = map(int, input().split())goods = []for i in range(n): goods.append([int(i) for i in input().split()])dp = [0 for i in range(v+1)]for i in range(n): for j in range(v+1): # 从前往后 if j >= goods[i][0]: dp[j] = max(dp[j], dp[j-goods[i][0]]+goods[i][1])print(dp[-1])# 测试代码5 101 22 33 44 55 620
下面是有关完全背包的题目
Leetcode 279. 完全平方数
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。示例 1:输入: n = 12输出: 3 解释: 12 = 4 + 4 + 4.示例 2:输入: n = 13输出: 2解释: 13 = 4 + 9
首先,明确dp,然后找dp的转移方程。
这里,dp[i]:表示完全平方数和为i的 最小个数。这个是没有任何问题的,关键是dp的转移方程。
对于Runsen这个菜鸟来说,也很快指的这是转移方程,就是i减去k 加上1。本质上就是斐波那契数列的一个变形。
d p [ i ] = m i n ( d p ( i ) , d p [ i − k ] + 1 ) , k 指 的 是 平 方 和 的 数 dp[i] = min(dp(i),dp[i-k] + 1) ,k 指的是平方和的数 dp[i]=min(dp(i),dp[i−k]+1),k指的是平方和的数
问题就转为了求n的最大平方和的序列。
i = 1nums = []while i*i <= n: nums.append(i*i) i = i + 1
然后就是完全背包的反例的问题了。那么这个动态规划的问题基本解决了。
n = int(input())i = 1nums = []while i*i <= n: nums.append(i*i) i = i + 1print(nums)# dp = [0] * (n+1) 是求最大值,[float('inf')] * (n+1)求最小值# 如果写成 dp = [0] * (n+1) ,那么永远0最小dp = [float('inf')] * (n+1)dp[0] = 0for i in range(1,n+1): # j 是平方数 for j in nums: if i
下面代码来源官方的动态规划,和Runsen的基本一样。
import mathdef numSquares(n): """ :type n: int :rtype: int """ square_nums = [i ** 2 for i in range(0, int(math.sqrt(n)) + 1)] dp = [float('inf')] * (n + 1) # bottom case dp[0] = 0 for i in range(1, n + 1): for square in square_nums: if i < square: break dp[i] = min(dp[i], dp[i - square] + 1) return dp[-1]
顺便补充一下:四平方定理: 任何一个正整数都可以表示成不超过四个整数的平方之和。 推论:满足四数平方和定理的数n(四个整数的情况),必定满足 n = 4 a ( 8 b + 7 ) n=4^a(8b+7) n=4a(8b+7)
这个自己是不知道的,大家想深入:https://leetcode-cn.com/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode/
下面是四平方定理的代码
def numSquares(self, n): """ :type n: int :rtype: int """ while n % 4 == 0: n /= 4 if n % 8 == 7: return 4 a = 0 while a**2 <= n: b = int((n - a**2)**0.5) if a**2 + b**2 == n: return (not not a) + (not not b) a += 1 return 3
Leetcode 300 最长上升子序列
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明:可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。对于Runsen这个菜鸟来说,关键还是怎么找出dp和转移方程,dp[i]
是第i
个最长上升子序列。那么
d p [ i ] = m a x ( d p [ i ] , d p [ k ] + 1 ) 其 中 0 < k < i − 1 dp[i] = max(dp[i], dp[k] + 1) 其中 0<k<i-1 dp[i]=max(dp[i],dp[k]+1)其中0<k<i−1
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: # 如果定义dp dp[i] 最长上升子序列 那么 dp[i] = max(dp[i], dp[k] + 1) 0nums[j]: dp[i] = max(dp[i], dp[j]+ 1 ) return max(dp)
Leetcode 322 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3 解释: 11 = 5 + 5 + 1 示例 2:输入: coins = [2], amount = 3
输出: -1零钱兑换实际上就是完全背包的题目,也可以看作下楼梯的问题的变种
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # 第一步:定义dp数组或变量,首先明确题目说每种硬币的数量是无限的,但是会给定一个固定的 amount 金额,我们需要用最少的硬币数凑出这个金额,如果是01背包问题就是[0]开始; # 因此这个是一个完全背包的题目,还是下楼梯的问题的变种。完全背包求最小,那么初始就要时最大 dp = [float('inf')] * (amount + 1) # 计算的起点 0 块钱当然是 0 dp[0] = 0 # 状态转移方程: f(11) = min(f(10),f(9),f(6)) + 1 for i in range(amount + 1): for j in coins: if i-j >=0 : dp[i] = min(dp[i],dp[i-j] + 1 ) if dp[amount] > amount: # 如果dp[amount] 是amount + 1 ,说明了没有匹配的方式 return -1 return dp[-1]
至此完全背包就到这里结束了,完全背包注意dp的定义,求最大还是最小,完全背包的关键词就次数是无限的
转载地址:https://maoli.blog.csdn.net/article/details/108611604 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!