using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct JyoutaiDef
{
internal List<int> DimList;
internal List<int> ValList;
internal int SumVal;
}
static Dictionary<int, int> CanSumMaxValDict = new Dictionary<int, int>();
static void Main()
{
int[,] NumArr1 = {{ 7, 53,183,439,863},
{497,383,563, 79,973},
{287, 63,343,169,583},
{627,343,773,959,943},
{767,473,103,699,303}};
int[,] NumArr2 = {{ 7, 53,183,439,863,497,383,563, 79,973,287, 63,343,169,583},
{627,343,773,959,943,767,473,103,699,303,957,703,583,639,913},
{447,283,463, 29, 23,487,463,993,119,883,327,493,423,159,743},
{217,623, 3,399,853,407,103,983, 89,463,290,516,212,462,350},
{960,376,682,962,300,780,486,502,912,800,250,346,172,812,350},
{870,456,192,162,593,473,915, 45,989,873,823,965,425,329,803},
{973,965,905,919,133,673,665,235,509,613,673,815,165,992,326},
{322,148,972,962,286,255,941,541,265,323,925,281,601, 95,973},
{445,721, 11,525,473, 65,511,164,138,672, 18,428,154,448,848},
{414,456,310,312,798,104,566,520,302,248,694,976,430,392,198},
{184,829,373,181,631,101,969,613,840,740,778,458,284,760,390},
{821,461,843,513, 17,901,711,993,293,157,274, 94,192,156,574},
{ 34,124, 4,878,450,476,712,914,838,669,875,299,823,329,699},
{815,559,813,459,522,788,168,586,966,232,308,833,251,631,107},
{813,883,451,509,615, 77,281,613,459,205,380,274,302, 35,805}};
int[,] NumArr = NumArr2;
var Stk = new Stack<JyoutaiDef>();
for (int I = 0; I <= NumArr.GetUpperBound(1); I++) {
JyoutaiDef WillPush;
WillPush.DimList = new List<int> { I };
WillPush.ValList = new List<int> { NumArr[0, I] };
WillPush.SumVal = NumArr[0, I];
Stk.Push(WillPush);
}
int MaxSumVal = 0;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (Popped.ValList.Count - 1 == NumArr.GetUpperBound(1)) {
if (MaxSumVal < Popped.SumVal) {
MaxSumVal = Popped.SumVal;
Console.WriteLine("解候補{0}を発見", MaxSumVal);
}
continue;
}
int CurrDim = Popped.ValList.Count;
for (int I = 0; I <= NumArr.GetUpperBound(1); I++) {
if (Popped.DimList.Contains(I)) continue;
JyoutaiDef WillPush;
WillPush.DimList = new List<int>(Popped.DimList) { I };
WillPush.ValList = new List<int>(Popped.ValList) { NumArr[CurrDim, I] };
WillPush.SumVal = Popped.SumVal + NumArr[CurrDim, I];
if (WillEdakiri(WillPush.DimList, WillPush.SumVal) == false)
Stk.Push(WillPush);
}
}
Console.WriteLine("答えは{0}", MaxSumVal);
}
//選択列の組み合わせと要素の合計で枝切り
static Dictionary<string, int> mEdakiriMemoDict = new Dictionary<string, int>();
static bool WillEdakiri(List<int> pDimList, int pSumNum)
{
var sb = new System.Text.StringBuilder();
foreach (int EachInt in pDimList.OrderBy(A => A))
sb.AppendFormat("{0},", EachInt);
string KeyStr = sb.ToString();
int wkGetVal;
if (mEdakiriMemoDict.TryGetValue(KeyStr, out wkGetVal))
if (wkGetVal >= pSumNum) return true;
mEdakiriMemoDict[KeyStr] = pSumNum;
return false;
}
}