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]