九章演算法 | Netflix 面試題:Surplus Value Backpack

九章演算法 | Netflix 面試題:Surplus Value Backpack

來自專欄 九章演算法 - lintcode/leetcode題解

撰文 | JZ

專欄 | 九章演算法

題目描述

有一個容量為 c 的背包。有 n 個 A 類物品,第 i 個 A 類物品的體積為 a[i],物品的價值為裝入該物品後背包剩餘容量 * k1。有 m 個 B 類物品,第 i 個 B 類物品的體積為 b[i],物品的價值為裝入該物品後背包剩餘容量 * k2。求最大可以獲得的價值。

思路點撥

首先要知道對於 A 類物品和 B 類物品都是按體積從小到大放最優,然後剩下的就是一個二維的dp了。

考點分析

這題相對來說比較困難,是變形的背包問題,可以說是貪心+dp。設 dp[i][j] 代表A類的前i個物品,B類的前j個物品選擇若干個可以得到的最大價值,則有 dp[i][j] = max(dp[i - 1][j] + (c-suma[i]-sumb[j]) * k1, dp[i][j - 1] + (c - suma[i] - sumb[j]) * k2)。

九章參考程序

jiuzhang.com/solution/s

推薦閱讀:

TAG:演算法 | IT行業 | 數據結構 |