ナップサック問題 アルゴリズム

Question

現在javaを用いて再帰の学習をしています。
再帰がよくわかりません。
具体例として
ナップサック問題を解く再帰的なアルゴリズムを教えてください。

Answer 1

こんなんいかがでしょう。

package a;

import java.util.ArrayList;
import java.util.List;

public class TT10780 {
	public static void main(String[] args) {
		try {
			Item[] items = new Item[] {
					new Item("A", 20, 10),
					new Item("B", 28, 13),
					new Item("C", 16, 8),
					new Item("D", 8, 5),
					new Item("E", 12, 7),
					new Item("F", 24, 11),
			};

			for(Item i : new HiPriceCombi(items, 30).get()) {
				System.out.println(i.name);
			}
		}
		catch(Throwable e) {
			e.printStackTrace();
		}
	}

	public static class Item {
		public Item(String n, int p, int w) {
			name = n;
			price = p;
			weight = w;
		}

		public String name;
		public int price;
		public int weight;
	}

	public static class HiPriceCombi {
		private Item[] items;
		private int weightCapa;

		public HiPriceCombi(Item[] i, int w) {
			items = i;
			weightCapa = w;
		}

		private int price;
		private int weight;
		private List<Item> combi;

		private int hiPrice;
		private Item[] hiPrCombi;

		public Item[] get() {
			price = 0;
			weight = 0;
			combi = new ArrayList<Item>();
			hiPrCombi = null;
			pick(0);
			return hiPrCombi;
		}

		/**
		 * 再帰メソッド
		 */
		private void pick(int bgnPos) {
			for(int index = bgnPos; index < items.length; index++) {
				Item item = items[index];

				if(weight + item.weight <= weightCapa) {
					price += item.price;
					weight += item.weight;
					combi.add(item);

					if(hiPrCombi == null || hiPrice < price) {
						hiPrice = price;
						hiPrCombi = combi.toArray(new Item[0]);
					}
					pick(index + 1); // ★★★再帰★★★

					price -= item.price;
					weight -= item.weight;
					combi.remove(combi.size() - 1);
				}
			}
		}
	}
}