0

実際にどの程度の変動があるかはわかりませんが、ここに問題があります。

あなたは長い旅に出ようとしています。その前に、荷物をまとめる必要があります。持ち運べる N 個のアイテムがあります。各アイテムには、その有用性を表す重量と値があります。K キログラムを超えるものを運ぶことはできません。所持できるアイテムの最大合計金額はいくらですか? （各アイテム1点のみお持ちいただけます。）

DP を使用して問題を解決すると思われるアルゴリズムを作成しましたが、うまくいくかどうかはわかりません。注: 疑似コードとアルゴリズムの組み合わせに似ていますが、書き方もよくわかりません。

k が最大重みであると仮定します。2 つの配列: 1 つは各アイテムの重み w[] を含み、もう 1 つは値 v[] を含みます。

 for i = 0; i<numberOfItems; i++
 {
    value = 0
    k = MaxWeight;
    for(j = i; j<numberOfItems; j++
    {
        if(j = i)
        {
            if(k - w[i] >= 0)
            {
                k = k-w[i]
                value = value + v[i]
            }
        }
        else
        {
            if(k - w[j] >= 0)
            {
                k = k-w[j]
                value = value + v[j]
            }
        }
    }
}
4

1 に答える 1

3

いいえ、貪欲なアルゴリズムは機能しません。

この例を確認してください：

MaxWeight = 12
Items = 4 5 4 4 (each value is 1)

アルゴリズムは項目 1 と 2 (または項目 2 と 3、または 3 と 4) を選択します。最適な解決策は、項目 1、3、および 4 を使用することです。

于 2013-08-02T10:51:48.520 に答える