九章演算法 | Netflix 面試題:Surplus Value Backpack
05-21
九章演算法 | 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)。
九章參考程序
https://www.jiuzhang.com/solution/surplus-value-backpack/
推薦閱讀: