0

Weights[]および と一緒にアイテムのリストを取得したとしPrice[]ます。2 つの整数が与えられた場合、購入したアイテムの総重量が K に正確に等しく、アイテムの数が N を超えないように、必要な最小金額を見つける必要がありますN<=100。K<=100を印刷するだけIMPOSSIBLEです。各商品は何度でもご購入いただけます。

この問題にナップザックを適用する方法と、ナップザックの問題でない場合の解決方法を教えてください。

4

2 に答える 2

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)

の場合dp[K] != infinity、それが解決策です。それ以外の場合、解決策はありません。実際の効率は、計算方法によって異なりますMaxWeight。すべてのアイテムの重量を合計するか、それについてより賢くしようとします。

于 2012-07-27T09:52:48.533 に答える
1

ナップザックの問題ではなく、動的プログラミング (DP) ソリューションが必要です。ただし、ナップサックには DP ソリューションがあります。

あなたのケースの解決策は、必要な再発を形成することです。お金を最小限に抑えることを目標にしているため、状態遷移ごとに重量と品目番号が追加され、新しい状態が形成されます。

したがって、状態空間は次のとおりです。DP[Weight][Item]

コーディングは演習として残します。

于 2012-07-27T09:55:33.690 に答える