讓我們想象一下，我必須在背包里裝滿受約束的物品：
- 每個專案都有一個相關的權重 wi 和利潤 pi
- 最大總重量 Wmax
知道：
- 有專案類別，我必須從每個類別中選擇一個專案
- 當然，目的是選擇專案以最大化利潤總和
示例：Wmax=400
| 圖書 | 書籍重量 | 圖書利潤 | 食物 | 食物重量 | 食品利潤 |
|---|---|---|---|---|---|
| 圣經 | 500 | 25 | 起司 | 80 | 120 |
| 小王子 | 150 | 5 | 香蕉 | 250 | 200 |
在這里，最好的解決方案是（小王子，香蕉）
我有一個類似的問題，我想找出最好的編碼方法，但我不知道這是什么版本/變體，它是已知的變體嗎？
uj5u.com熱心網友回復：
我不確定是否存在與您的匹配的現有變體，但很容易從經典變體中得出推論并解決這個問題。
經典變體具有 2D 動態規劃（DP[N][W]，其中N和W是專案數和最大重量）。
在這個變體中，由于我們只能選擇每個類別中的一個，因此您可以使用 3D DP like ，它表示您可以從第一個具有重量的專案dp[i][w][j]中獲得的最大值，并且是一個 0/??1 int 表示類別編號中的專案是否具有被選中與否。iwjj
我將離開實作，因為遞回關系相對簡單并且與經典變體非常相似。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446412.html
下一篇：排序陣列串列的arraylist