梅隆銷售農民的算法

Question

問題我在網上看到： 一個賣瓜的農民有n個瓜。每個甜瓜的重量，一個整數（磅），是不同的。一位顧客要求準確的m磅未切割的瓜。現在，農民有以下問題：如果能夠滿足顧客，他應該儘可能有效地找到合適的瓜子，或者告訴顧客不能滿足他的要求。

注意：這不是家庭作業順便說一句，我只是需要指導。

我的答案： 這似乎類似於硬幣更換問題（揹包）和子集問題（回溯）。 硬幣改變：我可以把權重放到一個集合w = {5，8，3，2，....}然後求解，子集問題也一樣。

所以基本上我可以使用任何一種方法來解決這個問題？

Answer 1

這完全是一個整數揹包問題，其中解決方案沒有浪費。有一個很好的動態編程/記憶策略來幫助你解決它。見任一鏈接：

http://www.cs.ship.edu/~tbriggs/dynamic/

https://en.wikipedia.org/wiki/Knapsack_problem

事實上，子集和問題，其中重量等於每個項目價值的0/1揹包問題。