ナップサック問題とは価値と重量をもつ n 種類の荷物が与えられたとき、重量の合計が W を超えない範囲で選択した荷物の価値の合計を最大にするにはどのように選べばよいか」という整数計画問題です。
そのなかでも同じものをナップサック問題において各荷物を1つまでしか選ぶことができない問題を 0-1 ナップサック問題 といいいます。
どのようにして解を導き出せばよいのでしょうか？
「1つも荷物を選べない」あるいは「最大重量が 0」であるときには、詰め込める荷物がないので選ばれた荷物の価値の合計を 0 とする。
荷物 iの重さが w を超えている場合は、荷物 iは追加できないから、価値の合計は荷物の添字の上限が1つ前までのものの価値の最大値になる
荷物 iの重さが wを越えていない場合には、品物 iを追加しない場合と追加をする場合の価値のなかから大きいものを選ぶ。
ここでは0-1 ナップサック問題を考えます。
|
1 2 3 4 5 |
(重さｗ、価値v) = (2, 4), (2, 5), (1, 2), (3, 8) |
とし、荷物の数nを4，ナップザックの容量maxWeightを5にします。
最初の一行でnとmaxWeightを表わし、次の行から半角区切りでそれぞれの荷物の重さと価値を表わします。
|
1 2 3 4 5 |
4 5 // 荷物の数と最大重量 2 4 // 重さ2、価値4の荷物 2 5 // 重さ2、価値5の荷物 1 2 // 重さ1、価値2の荷物 3 8 // 重さ3、価値8の荷物 |
出力は以下のようになります。
|
1 2 3 |
13 (w = 3, v = 8) を持っていきます。 (w = 2, v = 5) を持っていきます。 |
まず重さと価値をセットで管理できるようにItemクラスを定義します。
|
1 2 3 4 5 6 7 8 9 10 11 |
public class Item { public Item(int w, int v) { Weight = w; Value = v; } public int Weight { get; } public int Value { get; } } |
フィールド変数は荷物の種類の数、ナップサックに積めることができる最大重量、Itemオブジェクトのリスト Itemsです。
SetItemsメソッドはフィールド変数に必要な値をセットし、Itemオブジェクトのリスト Itemsにオブジェクトを格納します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Program { static int N = 0; // 要素の数 static int MaxWeight = 0; // 最大重量 static List<Item> Items = new List<Item>(); static void SetItems() { string[] NW = Console.ReadLine().Split(); N = int.Parse(NW[0]); // 要素の数 MaxWeight = int.Parse(NW[1]); // 最大重量 List<int> values = new List<int>(); List<int> weights = new List<int>(); for (int i = 0; i < N; i++) { string[] vs = Console.ReadLine().Split(); weights.Add(int.Parse(vs[0]));// [i] = item[0]; values.Add(int.Parse(vs[1]));// [i] = item[0]; } for (int i = 0; i < N; i++) Items.Add(new Item(weights[i], values[i])); } } |
プログラムが開始されたらSetItemsメソッドで必要な値をフィールド変数に格納したあとソートし、ジャグ配列を生成して、上記アルゴリズムにそって値を確定していきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class Program { static void Main() { SetItems(); // 入れることができる荷物の最大価値だけを知るだけなら必要ない Items = Items.OrderBy(x => x.Value).ThenByDescending(x => x.Weight).ToList(); int[][] dp = new int[N + 1][]; for (int i = 0; i < N + 1; i++) dp[i] = new int[MaxWeight + 1]; for (int i = 0; i < N; i++) { for (int w = 0; w <= MaxWeight; w++) { if (w >= Items[i].Weight) { // 荷物 iの重さが wを越えていない場合には、 // 荷物 iを追加しない場合と追加をする場合の価値のなかから大きいものを選ぶ。 dp[i + 1][w] = Math.Max(dp[i][w - Items[i].Weight] + Items[i].Value, dp[i][w]); } else { // 荷物 iの重さが w を超えている場合は、荷物 iは追加できないから、 // 価値の合計は荷物の添字の上限が1つ前までのものの価値の最大値になる // dp[i + 1][w] = dp[i][w]; } } } int ans = dp.Last().Last(); Console.WriteLine("解：" + ans); // これで終わりだがいろいろ表示させてみる ShowInfo(dp, ans); } } |
ジャグ配列のdp.Last().Last()を調べれば積めることができる荷物の価値の最大値はわかるのですが、どの荷物を入れるのかも表示させます。また上記アルゴリズムにそって値を確定していく様子も可視化します。
最後に配列に追加された荷物は表示されているので、答えからその値だけ減らします。減らした値が上の配列のなかにあればそこから追加された価値だけ減らして上へとたどっていきます。存在しない場合はその上の配列で追加された価値で同じことができないか試します。0までたどることができたらナップサックにいれることができる荷物を取得できたことになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Program { static void ShowInfo(int[][] dp, int ans) { Console.WriteLine(""); // 入力された値を表示させる Console.WriteLine($"N = {N}, maxWeight = {MaxWeight}"); for (int i = 0; i < Items.Count; i++) Console.WriteLine($"w = {Items[i].Weight}, v = {Items[i].Value}"); Console.WriteLine(""); int len = dp.Length; for (int i = 0; i < len; i++) { string s = string.Join(", ", dp[i]); if (i - 1 >= 0) Console.WriteLine($"(w:{Items[i - 1].Weight}, v:{Items[i - 1].Value}) を追加\t{s}"); else Console.WriteLine($"何も追加されていない\t{s}"); } Console.WriteLine(""); for (int i = len - 1; i >= 0; i--) { string s = string.Join(", ", dp[i]); if (i - 1 >= 0) { int newAns = ans - Items[i - 1].Value; // ans から items[i - 1].Value を引いたものがdp[i - 1]のなかにあるか調べる if (dp[i - 1].Any(_ => _ == newAns)) { // あるならそれはナップサックにいれた荷物 Console.WriteLine($"(w = {Items[i - 1].Weight}, v = {Items[i - 1].Value}) を持っていきます。"); ans -= Items[i - 1].Value; // ans == 0 になるまで繰り返す if (ans <= 0) break; } else { Console.WriteLine("not find " + newAns + " in " + string.Join(", ", dp[i - 1])); // 見つからない場合は i をひとつ減らして同じことを繰り返す } } } } } |
