ナップサック問題(C#)

入力

public class Item // アイテム
{
	public int Value;  // このアイテムの価値 : 0 ～ 1,000,000 の範囲でランダムに生成
	public int Weight; // このアイテムの重さ : 0 ～     1,000 の範囲でランダムに生成
}

public class Condition // 与えられた条件
{
	public Item[] Items;       // 選択可能なアイテムリスト : 個数 0 ～ 1,000 の範囲でランダムに生成
	public int WeightCapacity; // 最大総重量               :      0 ～ 1,000 の範囲でランダムに生成
}

Solve0001

総当りで解く

public static Item[] Solve0001(Condition cond)
{
	Item[] best = null;
	bool[] selecteds = new bool[cond.Items.Length];
	bool forward = true;
	int index = 0;

	for (; ; )
	{
		if (forward)
		{
			if (cond.Items.Length <= index)
			{
				Item[] selectedItems = Enumerable.Range(0, cond.Items.Length).Where(i => selecteds[i]).Select(i => cond.Items[i]).ToArray();

				if (selectedItems.Select(item => item.Weight).Sum() <= cond.WeightCapacity)
					if (best == null || best.Select(item => item.Value).Sum() < selectedItems.Select(item => item.Value).Sum())
						best = selectedItems;

				forward = false;
			}
			else
			{
				selecteds[index] = true;
			}
		}
		else
		{
			if (selecteds[index])
			{
				selecteds[index] = false;
				forward = true;
			}
		}

		if (forward)
		{
			index++;
		}
		else
		{
			if (index <= 0)
				break;

			index--;
		}
	}
	return best;
}

Solve0002

動的計画法？で解く

private class SelectedItem
{
	public int ItemIndex;
	public int TotalValue;
	public SelectedItem Prev;
}

public static Item[] Solve0002(Condition cond)
{
	SelectedItem[,] table = new SelectedItem[cond.Items.Length, cond.WeightCapacity + 1];
	SelectedItem best = null;
	SelectedItem seli;

	for (int i = 0; i < cond.Items.Length; i++)
	{
		if (cond.Items[i].Weight <= cond.WeightCapacity)
		{
			table[i, cond.Items[i].Weight] = seli = new SelectedItem()
			{
				ItemIndex = i,
				TotalValue = cond.Items[i].Value,
				Prev = null,
			};

			if (best == null || best.TotalValue < seli.TotalValue)
				best = seli;
		}
	}
	for (int i = 0; i < cond.Items.Length; i++)
	{
		for (int w = 0; w <= cond.WeightCapacity; w++)
		{
			if (table[i, w] != null)
			{
				for (int ni = i + 1; ni < cond.Items.Length; ni++)
				{
					int nw = w + cond.Items[ni].Weight;

					if (nw <= cond.WeightCapacity)
					{
						int nv = table[i, w].TotalValue + cond.Items[ni].Value;

						if (table[ni, nw] == null || table[ni, nw].TotalValue < nv)
						{
							table[ni, nw] = seli = new SelectedItem()
							{
								ItemIndex = ni,
								TotalValue = nv,
								Prev = table[i, w],
							};

							if (best == null || best.TotalValue < seli.TotalValue)
								best = seli;
						}
					}
				}
			}
		}
	}
	List<Item> ret = new List<Item>();

	while (best != null)
	{
		ret.Add(cond.Items[best.ItemIndex]);
		best = best.Prev;
	}
	return ret.ToArray();
}

Extra

テスト用コード

public const int ITEM_VALUE_MIN = 0;
public const int ITEM_VALUE_MAX = 1000000;

public const int ITEM_WEIGHT_MIN = 0;
public const int ITEM_WEIGHT_MAX = 1000;

public const int ITEM_COUNT_MIN = 0;
//public const int ITEM_COUNT_MAX = 1000;

public const int WEIGHT_CAPACITY_MIN = 0;
public const int WEIGHT_CAPACITY_MAX = 1000;

public class Item
{
	public int Value;
	public int Weight;
}

public class Condition
{
	public Item[] Items;
	public int WeightCapacity;
}

public static Condition MakeCondition(int itemCountMax)
{
	Condition cond = new Condition();

	cond.Items = new Item[SecurityTools.CRandom.GetRange(ITEM_COUNT_MIN, itemCountMax)];
	cond.WeightCapacity = SecurityTools.CRandom.GetRange(WEIGHT_CAPACITY_MIN, WEIGHT_CAPACITY_MAX);

	for (int index = 0; index < cond.Items.Length; index++)
	{
		cond.Items[index] = new Item()
		{
			Value = SecurityTools.CRandom.GetRange(ITEM_VALUE_MIN, ITEM_VALUE_MAX),
			Weight = SecurityTools.CRandom.GetRange(ITEM_WEIGHT_MIN, ITEM_WEIGHT_MAX),
		};
	}
	return cond;
}

/// <summary>
/// 動作テスト
/// </summary>
public static void Test01()
{
	int testCnt = 0;

	while (Console.KeyAvailable == false)
	{
		Console.WriteLine("testCnt: " + (++testCnt));

		Condition cond = MakeCondition(17);
		//Condition cond = MakeCondition(18);
		//Condition cond = MakeCondition(19);
		//Condition cond = MakeCondition(20);

		Item[] ret1 = Solve0001(cond);
		Item[] ret2 = Solve0002(cond);

#if false
		// 最善の組み合わせが複数ある場合、異なる組み合わせを選ぶ可能性がある。

		if (ret1.Length != ret2.Length)
			throw null; // different !!!

#if false
		// 並びが一致するとは限らない。

		if (Enumerable.Range(0, ret1.Length).Any(index => ret1[index] != ret2[index]))
			throw null; // different !!!
#else
		if (ret1.Any(item => ret2.Contains(item) == false))
			throw null; // different !!!
#endif
#else
		if (ret1.Select(item => item.Value).Sum() != ret2.Select(item => item.Value).Sum())
			throw null; // different !!!
#endif
	}
}

/// <summary>
/// 速度テスト
/// </summary>
public static void Test02()
{
	int testCnt = 0;

	while (Console.KeyAvailable == false)
	{
		Console.WriteLine("testCnt: " + (++testCnt));

		Condition cond = MakeCondition(1000);

		DateTime stTm = DateTime.Now;
		Solve0002(cond);
		DateTime edTm = DateTime.Now;

		Console.WriteLine("実行時間 = " + (edTm - stTm).TotalMilliseconds.ToString("F3") + " ミリ秒");
	}
}

// Solve0001() 省略
// Solve0002() 省略