バックパックの梱包について少し

多くの人々は、いわゆるバックパックの梱包作業を知っています。

簡単に思い出させてください。オブジェクトの山から、バックパックを眼球に詰め込み、それでも発射できるように選択する必要があります。

より形式的に言えば、数字のペアAのセットA（i）b（i）から、数字aの合計が所定のSを超えず、数字bの合計が最大になるように選択する必要があります。 Σa（n）≤S、Σb（n）= max。



ソースセット：

											Σ
a	3	14	25	26	32	2	28	23	1	9	163
b	11	12	5	30	31	25	19	27	32	33	225

最後の列には、すべてのアイテムの総重量Σaとそれらの総コストΣbが表示されます。 セットS（キャリングキャパシティ）はΣaを超えてはなりません。それ以外の場合、解決策は簡単です。 これらの制限がある場合、総コストΣbを使用して、結果のソリューションの総コストが絶対最大値とどの程度異なるかを評価できます。



この問題を解決する方法はいくつかありますが、それらはウィキペディアで説明されています。

「貪欲な」アルゴリズムに興味があります。

これは、各ペアに対して値d = a / bを計算することで構成され、それによってペアがソートされてから選択されます。



値セットd：

											Σ
a	3	14	25	26	32	2	28	23	1	9	163
b	11	12	5	30	31	25	19	27	32	33	225
d	3.67	0.86	0.2	1.15	0.97	12.5	0.68	1.17	32,0	3.67

dセットでソート

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	11	33	27	30	31	12	19	5	225
d	32,0	12.5	3.67	3.67	1.17	1.15	0.97	0.86	0.68	0.20

S = 60で解を見つけてみましょう。

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	11	33	27	30	31	12	19	5	225
d	32,0	12.5	3.67	3.67	1.17	1.15	0.97	0.86	0.68	0.20

最初の5つの項目から、Σa= 38、Σb= 128が得られます。 次の項目は適合しません。 それにより、Σa= 64。

最初の5つのオブジェクトを配置した後に残った穴のサイズは、60-38 = 22でした。 セットを最後まで見ると、この穴に別のオブジェクトが配置されています。

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	11	33	27	30	31	12	19	5	225
d	32,0	12.5	3.67	3.67	1.17	1.15	0.97	0.86	0.68	0.20

合計：Σa= 52、Σb= 140。



残念ながら、これは最適なソリューションではありません。



アイテム23-27を26-30に置き換えると、

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	11	33	27	30	31	12	19	5	225
d	32,0	12.5	3.67	3.67	1.17	1.15	0.97	0.86	0.68	0.20

Σa= 55、Σb= 143、これはすでに最適なソリューションです。



制限的なケースを検討してください。 バックパックには個別に配置された2つのアイテムがありますが、一緒にはありません。 当然の解決策は、重量が大きいにもかかわらず、より高価なアイテムを取ることです。 明らかに、積み上げられたアイテムの価格は重量よりも優先されます。

dの値を少し再評価することで、必要な方向に優先順位をシフトできます。



単純な比率d = b / aの代わりに、d = b ² / aを取り、それでもdでソートします。



d = b ² / aセットでソート

											Σ
a	1	2	9	3	26	23	32	14	28	25	163
b	32	25	33	11	30	27	31	12	19	5	225
d	1024	312.5	121	40.33	34.6	31.7	30,0	10.3	12.9	1,0

同じS = 60の場合

											Σ
a	1	2	9	3	26	23	32	14	28	25	163
b	32	25	33	11	30	27	31	12	19	5	225
d	1024	312.5	121	40.33	34.6	31.7	30,0	10.3	12.9	1,0

Σa= 55、Σb= 143。 すぐに最適なソリューションに到達します。



したがって、バックパックを置くタスクは線形時間で解決され、完全なNPではありません。