Description
一个背包有一定的承重cap,有N件物品,每件都有自己的价值,记录在数组v中,也都有自己的重量,记录在数组w中,每件物品只能选择要装入背包还是不装入背包,要求在不超过背包承重的前提下,选出物品的总价值最大。
给定物品的重量w价值v及物品数n和承重cap。请返回最大总价值。
测试样例:
[1,2,3],[1,2,3],3,6
返回:6
Solutions
1. DP
# Time: O(mn)
# Space: O(mn)
class Backpack:
def maxValue(self, w, v, n, cap):
dp = [[0 for _ in range(cap + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, cap + 1):
if w[i-1] <= j:
dp[i][j] = max(dp[i - 1][j - w[i-1]] + v[i-1], dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
return dp[n][cap]