初识动态规划01背包问题
# 动态规划
动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题,例如斐波那契数列,如果运用递归的方式来求解会重复计算很多相同的子问题,利用动态规划的思想可以减少计算量。
# 1.最优子结构
「最优子结构」是某些问题的一种特定性质,并不是动态规划问题专有的。想满足最优子结构,子问题之间必须互相独立。
举个例子,比如,求一个班上的某个同学成绩最好,这就是最优子结构,而如果是求一个班上成绩第二名的,就不是了,为什么呢?因为第二名的,可能在一个小组里面是最好的,但是在全班上就可能不是成绩最好的,而如果在班上成绩最好的,那肯定在小组内,成绩也是最好的。
如果子问题不相互独立,就不符合最优子结构,不过有些情况也可以改造问题,使其成为最优子结构,最优子结构性质作为动态规划问题的必要条件,一定是让你求最值的。
# 2.dp数组的遍历方向
有的时候,我们需要对dp数组的遍历方向做一些改变,有时候是正向,反向,斜向。
而01背包问题应该从后往前反向遍历,因为每个物品(或者说数字)只能用一次,以免之前的结果影响其他的结果。
# 3.动态规划框架
因为递归树,常常会出现子问题重叠,为了剪枝,有时候需要用备忘录递归解法,还有就是dp数组的迭代解法,DP table使用的是自底向上思想,备忘录是自顶向下,备忘录更像是一颗递归树,每次解决问题,最好是画出该问题的递归树,然后查找规律,找出最短路径,拿到最优解。
第一步:明确「状态」和「选择」。
如何才能描述一个问题局面?只要给几个物品和一个背包的容量限制,就形成了一个背包问题呀。所以状态有两个,就是「背包的容量」和「可选择的物品」。
再说选择,也很容易想到啊,对于每件物品,你能选择什么?选择就是「装进背包」或者「不装进背包」嘛。
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 择优(选择1,选择2...)
接下来就解决下01背包的问题吧~
# 01背包一维
输入
15;15,15;7,2;8,14
其中15是你每周的休闲时间
15,15 表示泡第1个妹子(撩第1个汉子)需要15分钟能获取15的幸福感
7,2 表示泡第2个妹子(撩第2个汉子)需要7分钟能获取2的幸福感
8,14 表示泡第3个妹子(撩第3个汉子)需要8分钟能获取14的幸福感
输出
输出是你能获得最大的幸福感
16
你同时泡(撩)第2个和第3个妹子(汉子),消耗7+8=15分钟,能获得最大的幸福感2+14=16
因为做题的平台没有自己熟悉的js,只能用python了:
def knapsack(s):
s = s.split(";")
c = int(s[0])
step = 0
girls = [None] * (len(s)-1)
for i in range(1,len(s)):
s_s = s[i]
s_s = s_s.split(",")
girls[i-1] = [int(s_s[0]), int(s_s[1])]
step += 1
dp = [0]*(c+1)
# 套用状态框架
# for状态1「可选择的物品」
for i in range(step):
girl = girls[i]
t = girl[0]
v = girl[1]
# for状态2「花费的时间」
# 这里是反向遍历
for j in range(len(dp)-1,0,-1):
if j>=t:
v1 = dp[j-t]+v
v2 = dp[j]
dp[j] = max(v1,v2)
print max(dp)
a = raw_input()
knapsack(a)
# 01背包二维
二维的背包仅仅是多了一层而已,不过有个地方需要注意,数组用乘法构成,只是浅拷贝,应该用生成器生成。
输入
包含你每周的休闲时间(分钟)和可用金钱(元),还有若干个妹子(汉子)需要消耗的时间和能获取到的幸福感
15,8;15,8,15;7,6,2;8,2,14
其中15是你每周的休闲时间
8表示你每周可用金钱为8元
15,8,15 表示泡第1个妹子(撩第1个汉子)需要15分钟花费8元能获取15的幸福感
7,6,2 表示泡第2个妹子(撩第2个汉子)需要7分钟花费6元能获取2的幸福感
8,2,14 表示泡第3个妹子(撩第3个汉子)需要8分钟花费2元能获取14的幸福感
输出
16
你同时泡(撩)第2个和第3个妹子(汉子),消耗7+8=15分钟,花费6+2=8元,能获得最大的幸福感2+14=16
代码:
def knapsack(s):
s = s.split(";")
my_time = int(s[0].split(",")[0])
my_money = int(s[0].split(",")[1])
step = 0
girls = [None] * (len(s)-1)
for i in range(1,len(s)):
s_s = s[i]
s_s = s_s.split(",")
girls[i-1] = [int(s_s[0]), int(s_s[1]),int(s_s[2])]
step+=1
# 这个是浅拷贝的用法 如果是一维的话还好 二维的话就会出bug 一直遍历的都是同一个
# dp = [[0]*(my_money+1)]*(my_time+1)
dp = [[0 for i in range(my_money+1)] for i in range(my_time+1)]
# 套用状态框架
# for状态1「可选择的物品」
for i in range(step):
girl = girls[i]
t = girl[0]
m = girl[1]
v = girl[2]
# for状态2「花费的时间」
for j in range(len(dp)-1,0,-1):
# for状态3「花费的金钱」
for k in range(len(dp[i])-1,0,-1):
if k>=m and j>=t:
# dp[状态1][状态2][...] = 择优(选择1,选择2...)
dp[j][k] = max(dp[j][k],dp[j-t][k-m]+v)
print max(max(dp))
a = raw_input()
knapsack(a)
这就是自己初识动态规划的一点感想,其实有很多还是抄大佬的想法,不过大佬总结的框架就像是公式一样,往里套就对了,而且我还发现了一个规律,这框架还符合数学的函数,可以约去相同的一项,比如:
上面的二维其实原本是三维的,原本这样dp[i][j][k] = max(dp[i][j][k],dp[i]dp[j-t][k-m]+v),不过用了数学的函数特性,等号左右两边相同的表达式可以约去,因为左右两边都有个公共的dp[i],故约去后,就变成了降维dp[j][k] = max(dp[j][k],dp[j-t][k-m]+v),一维的dp也是同样的道理,如果不降维,内存可是会超了的,我一开始就没降维,所以超内存了。