2

次のように、5 つのアイテム (名前、サイズ、値) があるとします。

("ITEM01", 100, 10000)
("ITEM02", 24, 576)
("ITEM03", 24, 576)
("ITEM04", 51, 2500)
("ITEM05", 155, 25)

そして、合計サイズが 150 に最も近いものを取得する必要があります (各アイテムは 1 回しか追加できません)。

これはナップザック問題と非常によく似ていますが、この場合の私の好ましい解決策は でありITEM01、ITEM04合計サイズが 151 になるため、完全ではありません (ナップザック問題により、サイズ = 150 を超えることITEM01はITEM02なくなりITEM03、合計サイズは になります)。 148)。

この問題に名前はありますか？（まだcombinatorial optimisationですか）？Python ソリューションを探していますが、探しているものの名​​前を知っていれば役立ちます。

4

2 に答える 2

2

動的計画法を使用してそれを行うことができます。

サイズdp[k]の合計が に等しいアイテムのリストに等しいとしkます。最初d[0] = []と. dp[k] = None_ k > 0リストのサイズは、すべての要素のサイズの合計によって制限される場合があります。これを と呼びましょうS。

アルゴリズムが行うitemことは、 から までi = Sのそれぞれについて、 であるi = 0かどうかをチェックすることです。dp[i] != Noneつまり、サイズの合計が に等しいアイテムを選択できることがわかっていますi。これらのアイテムはリストにありますdp[i]。itemcurrentをそのリストに追加して、合計が に等しいアイテムのセットを持つことができることを観察しましょうi + item.size。したがって、 を割り当てdp[i + item.size] = dp[i] + [item]ます。すべてのアイテムを処理したら、目的のサイズの合計から開始し、両方向に移動して最も近い一致を見つける必要があります。

コード：

items = [("ITEM01", 100, 10000), ("ITEM02", 24, 576), \
    ("ITEM03", 24, 576), ("ITEM04", 51, 2500), ("ITEM05", 155, 25)]
S = sum([item[1] for item in items])
dp = [None for i in xrange(S + 1)]
dp[0] = []

for item in items:
    for i in xrange(S, -1, -1):
        if dp[i] is not None and i + item[1] <= S:
            dp[i + item[1]] = dp[i] + [item]

desired_sum = 150
i = j = desired_sum

while i >= 0 and j <= S:
    if dp[i] is not None:
        print dp[i]
        break
    elif dp[j] is not None:
        print dp[j]
        break
    else:
        i -= 1
        j += 1

出力：

[('ITEM01', 100, 10000), ('ITEM04', 51, 2500)]

ただし、このソリューションの複雑さは、アイテムの数とサイズの合計O(n*S)であるため、目的によっては遅すぎる場合があります。このソリューションで改善できるのは定数です。たとえば、サイズの合計を持つアイテムのセットを取得できることが保証されているため、 に設定できます(おそらく sum を持つ空のセット)。少なくとも 1 つのアイテムを取りたい場合は、すべてのアイテムの最小サイズをどこに取ることができます。nSSS2 * desired_sum[0, 2 * desired_sum]0S = max(min_item_size, 2 * desired_sum - min_item_size)min_item_size

編集：

ああ、あなたはまた、2 つの組み合わせが に等しく近いときに最大値を取得したいと考えていましたdesired_size。次に、サイズの合計ごとに最適な組み合わせを維持するために、コードを少し変更する必要があります。

すなわち：

if dp[i] is not None and i + item[1] <= S:

次のようにする必要があります。

if dp[i] is not None and i + item[1] <= S and \
    (
        dp[i + item[1]] is None
        or
        sum(set_item[2] for set_item in dp[i]) + item[2]
            > sum(set_item[2] for set_item in dp[i + item[1]])
    ):

(少し見にくいですが、見栄えを良くするために改行する方法がわかりません)

もちろん、毎回計算するのを避けるために、これらの合計を保持することもできます。

于 2013-03-20T11:52:10.157 に答える
0

作業中のナップザック ソルバーと多くの時間があると仮定します。

各アイテムの値を各アイテムの重量に設定し、容量が 150 のナップザックの問題を解きます。これにより、目標よりも小さい最大サイズ (この例では 148) が得られます。したがって、考慮すべき最大サイズは 150 + (150 - 148) = 152 です。

150 から 152 までの整数ごとにもう一度解いてください。差が小さい場合 (この例では 151) 停止し、それを使用して、元のアイテムの値を使用して値を解いてください。範囲が大きい場合は、二分探索を試すこともできます。

それ以外の場合は、元のナップザック問題を容量 148 と 152 で解き、最大の値を持つ解を選択します。

于 2013-03-20T16:23:52.780 に答える