返回可與一定量的購買獨特的項目

Question

我們已經在一個特定的順序排序幾個項目...... 所有項目相關的價格P（P1，P2 ... PN）說

物品1 - P1

item2 - p2

。 。 。

itemn - PN

我們要購買的物品x量。並且最初在每次迭代後x將變爲x-p1，x-（p1 + p2）... x-（p1 + p2 + ... pn）....在任何點，如果我們發現價格pk>當前值x的任何itemK我們將從列表中刪除該項目併購買下一個項目

我們將再次運行此操作直到x = 0（數量耗盡）或列表爲空（所有項目的值> x的當前值並從列表中刪除）

函數將返回no。每件商品的購買量

現在我可以想到一個基於python字典/列表的方法來做到這一點，我們將通過上述場景循環，執行.remove（item）適用的任何地方。

但它太多迭代餓了。想知道是否有更好的數學方法來有效地找到它。

Answer 1

這是你可以做的最好的。 （你提到的方式）。而且只需要一次傳球。沒有這樣的數學方法。

爲您的方法 - O(n) 1通。

檢查你的問題......這是一種模擬問題。這是你想要的嗎？ *。你從未提到過，如果你想最大化購買的物品。

但是，如果你想最大限度地提高項目的數量，那麼它是一個不同的問題級別。那麼你將不得不閱讀0-1 knapscak prblem。