AOJ本の読書メモ
AOJ
次のAOJの問題へ
前のAOJの問題へ
DPL_1_F: 0-1 Knapsack Problem II
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 5");
WillReturn.Add("4 2");
WillReturn.Add("5 2");
WillReturn.Add("2 1");
WillReturn.Add("8 3");
//13
}
else if (InputPattern == "Input2") {
WillReturn.Add("2 20");
WillReturn.Add("5 9");
WillReturn.Add("4 10");
//9
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct ItemInfoDef
{
internal long Value;
internal long Weight;
}
static List<ItemInfoDef> mItemInfoList = new List<ItemInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(InputList[0]);
long WeightLimit = wkArr[1];
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
ItemInfoDef WillAdd;
WillAdd.Value = wkArr[0];
WillAdd.Weight = wkArr[1];
mItemInfoList.Add(WillAdd);
}
long UB = mItemInfoList.Sum(pX => pX.Value);
// 最小の重さ[価値合計]なインラインDP表
long?[] DPArr = new long?[UB + 1];
DPArr[0] = 0;
foreach (ItemInfoDef EachItemInfo in mItemInfoList) {
for (long I = UB; 0 <= I; I--) {
if (DPArr[I].HasValue == false) continue;
long NewKey = I + EachItemInfo.Value;
long NewVal = DPArr[I].Value + EachItemInfo.Weight;
if (NewVal > WeightLimit) continue;
if (DPArr[NewKey].HasValue) {
if (DPArr[NewKey].Value <= NewVal) {
continue;
}
}
DPArr[NewKey] = NewVal;
}
}
var AnswerList = new List<long>();
for (long I = 0; I <= UB; I++) {
if (DPArr[I].HasValue) {
AnswerList.Add(I);
}
}
Console.WriteLine(AnswerList.Max());
}
}
解説
最小の重さ[価値合計]でインラインDPしてます。