選擇產品才能獲得鑑於在商店提供的產品列表最大車價值

Question

，我需要選擇設置的產品，我的車在這樣的方式，我的車值應爲最大就可以了。 限制就像，購物車的尺寸爲l*w*h。選擇的產品應單獨和完全裝入購物車，爲購物車提供最大可能的價值。每個產品可以選擇1個項目。

我有product id，price，l，w，ht，每個產品的weight我。這怎麼能完成？

我想出瞭如下邏輯。車的

1. 計算容積
使用它的價格
2. 排序基於價值/ CUCM的產品列表中的產品和每立方厘米產品的價值
3. 計算容積
4. 開始將產品從排序列表像第一，第二，第三等，直到購物車被裝滿。
5. 如果產品無法放入購物車，請跳過它並從排序列表中選擇下一個可能的產品。
6. 獲得列表後，檢查選定列表中的任何產品是否可以使用體積較小的其他產品替換，但會產生更多購物車價值。

但是，這並不讓我以最大的車值正確的產品清單。上述邏輯中的問題是什麼？

Answer 1

三維整數值是否具有一定的有限界？然後它可以通過動態編程來解決。但我認爲應該做出一些假設，例如子問題的劃分應該是端到端的切割平面等。沒有這種動態編程將是不可行的。

這裏的關鍵技巧是，你需要考慮，一個盒子可以通過多種方式定向的可能性，它是如何對準了自己的三個維度沿車的三個軸的數量。這是3！ =三個維度。因此，在處理第i個產品時的動態規劃中，包含所有6種方法將其3個維度解釋爲L，W，H。