798 · 背包问题VII - LintCode
描述
假设你身上有
n 元，超市里有多种大米可以选择，每种大米都是袋装的，必须整袋购买，给出每种大米的重量，价格以及数量，求最多能买多少公斤的大米样例
样例 1:
输入: n = 8, prices = [3,2], weights = [300,160], amounts = [1,6] 输出: 640 解释: 全买价格为2的米。
样例 2:
输入: n = 8, prices = [2,4], weight = [100,100], amounts = [4,2 ] 输出: 400 解释: 全买价格为2的米
法1 动态规划 多重背包
思路
在完全背包的基础上，多了一个条件：每样物品有数目限制。
因此状态转移的时候：
- 不考虑当前的物品
- 考虑当前物品，且考虑当前物品放几件到背包中。是在上一层的基础上开始放的
题解
class Solution: """ @param n: the money of you @param prices: the price of rice[i] @param weight: the weight of rice[i] @param amounts: the amount of rice[i] @return: the maximum weight """ def backPackVII(self, n, prices, weight, amounts): # write your code here # DP[i][j] 前 i 种大米花费 j 元可买到的最大重量 dp = [[0]*(n+1) for _ in range(len(prices)+1)] for i in range(1, len(dp)): for j in range(1, n+1): # j是背包空间（此题为金钱） dp[i][j] = dp[i-1][j] for k in range(0, amounts[i-1]+1): # k是第i类物品取几件,遍历每种可能 if j - k * prices[i-1] >= 0: dp[i][j] = max(dp[i][j], dp[i-1][j-k*prices[i-1]] + k * weight[i-1]) return dp[-1][n]