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]

References

  1. 12.8 01 背包问题