01 背包问题
#coding=utf-8
# 递归
class Solution(object):
def knapsack01(self, w, v,c):
"""
:type w: list
:type v: list
"""
length = len(w)
return self.bestValue(w,v,length-1,c)
# 用[0...index]的物品，填充容积为c的背包的最大价值
def bestValue(self,w,v,index,c):
# 函数的定义说明了初值
if index < 0 or c <= 0:
return 0
res = self.bestValue(w,v,index-1,c)
if w[index] <= c:
res = max(res,v[index] + self.bestValue(w,v,index-1,c-w[index]))
return res
# 记忆化递归
class Solution2(object):
def knapsack01(self, w, v, c):
"""
:type w: list
:type v: list
"""
length = len(w)
self.memo= [[-1 for i in range(c+1)] for i in range(length)]
return self.bestValue(w, v, length - 1, c)
# 用[0...index]的物品，填充容积为c的背包的最大价值
def bestValue(self, w, v, index, c):
if index < 0 or c <= 0:
return 0
if self.memo[index][c] != -1:
return self.memo[index][c]
res = self.bestValue(w, v, index - 1, c)
if w[index] <= c:
res = max(res, v[index] + self.bestValue(w, v, index - 1, c - w[index]))
self.memo[index][c] = res
return res
# 动态规划
class Solution3(object):
def knapsack01(self, w, v, c):
if not w :
return 0
length = len(w)
memo = [[-1 for i in range(c+1) ] for i in range(length)]
for i in range(c+1):
if w[0] <= i:
memo[0][i] = v[0]
else:
memo[0][i] = 0
for i in range(1,length):
for j in range(c+1):
memo[i][j] = memo[i-1][j]
if w[i] <= j:
memo[i][j] = max(memo[i][j] ,v[i] + memo[i-1][j-v[i]])
return memo[length-1][c]
# 01背包问题的空间优化
# 两行数组
class Solution4(object):
def knapsack01(self, w, v, c):
if not w:
return 0
length = len(w)
memo = [[-1 for i in range(c + 1)] for i in range(2)]
for i in range(c + 1):
if w[0] <= i:
memo[0][i] = v[0]
else:
memo[0][i] = 0
for i in range(1, length):
for j in range(c + 1):
memo[i%2][j] = memo[(i-1)%2][j]
if v[i] <= j:
memo[i%2][j] = max(memo[i%2][j], v[i] + memo[(i-1)%2][j - v[i]])
return memo[(length-1)%2][c]
# 01背包问题的空间优化
# 一行数组
class Solution5(object):
def knapsack01(self, w, v, c):
if not w:
return 0
length = len(w)
memo = [-1 for i in range(c + 1)]
for i in range(c + 1):
if w[0] <= i:
memo[i] = v[0]
else:
memo[i] = 0
for i in range(1, length):
for j in range(c,w[i]-1):
memo[j] = max(memo[j], v[i] + memo[j - v[i]])
return memo[c]