如何在這個算法難題中應用揹包法？

Question

假設你有一個物品清單及其Weights[]和Price[]。 現在給出兩個整數N<=100和K<=100你必須找到你應該花費的最小金額，使得你購買的物品的總重量完全等於K，物品的數量不超過N，如果它不可能滿足給定的條件只是打印一個IMPOSSIBLE。 您可以多次購買每件商品。

請告訴我如何在這個問題中應用揹包，如果它不是一個揹包問題，那麼如何解決它？

Answer 1

dp[i] = minimum money you have to pay to get weight i 

dp[_] = infinity 

for i = 1 to N do 
    for j = item[i].weight to MaxWeight do 
    dp[j] = min(dp[j], dp[j - item[i].weight] + item[i].price) 

如果是​​，那是您的解決方案，否則就沒有解決方法。實際效率取決於您計算MaxWeight的方式：或者對所有項目權重進行求和，或者嘗試對其進行更精確的設置。

Answer 2

你想要一個動態編程（DP）解決方案，而不是一個揹包問題。儘管Knapsack有一個DP解決方案。

您的案例的解決方案是形成必要的重現。既然你的目標是儘量減少金錢，每個州的轉變將增加重量和物品編號以形成一個新的狀態。

所以，你的狀態空間是：DP[Weight][Item]

編碼被留作練習。