結果
問題 | No.527 ナップサック容量問題 |
ユーザー | 明智重蔵 |
提出日時 | 2017-06-10 05:05:29 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 925 ms / 2,000 ms |
コード長 | 3,047 bytes |
コンパイル時間 | 986 ms |
コンパイル使用メモリ | 114,880 KB |
実行使用メモリ | 45,468 KB |
最終ジャッジ日時 | 2023-10-24 10:02:13 |
合計ジャッジ時間 | 10,266 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
25,860 KB |
testcase_01 | AC | 41 ms
25,860 KB |
testcase_02 | AC | 41 ms
25,864 KB |
testcase_03 | AC | 41 ms
25,860 KB |
testcase_04 | AC | 40 ms
25,768 KB |
testcase_05 | AC | 187 ms
31,736 KB |
testcase_06 | AC | 816 ms
44,200 KB |
testcase_07 | AC | 448 ms
44,204 KB |
testcase_08 | AC | 133 ms
29,300 KB |
testcase_09 | AC | 39 ms
25,768 KB |
testcase_10 | AC | 776 ms
44,304 KB |
testcase_11 | AC | 345 ms
37,900 KB |
testcase_12 | AC | 206 ms
32,580 KB |
testcase_13 | AC | 925 ms
45,468 KB |
testcase_14 | AC | 132 ms
29,012 KB |
testcase_15 | AC | 262 ms
34,836 KB |
testcase_16 | AC | 40 ms
25,860 KB |
testcase_17 | AC | 187 ms
31,948 KB |
testcase_18 | AC | 254 ms
34,328 KB |
testcase_19 | AC | 40 ms
25,860 KB |
testcase_20 | AC | 74 ms
26,904 KB |
testcase_21 | AC | 358 ms
39,848 KB |
testcase_22 | AC | 166 ms
31,084 KB |
testcase_23 | AC | 245 ms
34,756 KB |
testcase_24 | AC | 49 ms
25,872 KB |
testcase_25 | AC | 41 ms
25,872 KB |
testcase_26 | AC | 94 ms
27,876 KB |
testcase_27 | AC | 63 ms
25,992 KB |
testcase_28 | AC | 41 ms
25,872 KB |
testcase_29 | AC | 164 ms
31,464 KB |
testcase_30 | AC | 41 ms
25,872 KB |
testcase_31 | AC | 40 ms
25,864 KB |
testcase_32 | AC | 42 ms
25,864 KB |
testcase_33 | AC | 42 ms
25,872 KB |
testcase_34 | AC | 42 ms
25,864 KB |
testcase_35 | AC | 320 ms
37,188 KB |
testcase_36 | AC | 41 ms
25,864 KB |
testcase_37 | AC | 161 ms
30,532 KB |
testcase_38 | AC | 210 ms
32,828 KB |
testcase_39 | AC | 237 ms
33,876 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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("3"); WillReturn.Add("5 3"); WillReturn.Add("9 8"); WillReturn.Add("3 2"); WillReturn.Add("8"); //5 //7 } else if (InputPattern == "Input2") { WillReturn.Add("4"); WillReturn.Add("33 4"); WillReturn.Add("114 514"); WillReturn.Add("123 456"); WillReturn.Add("3 14"); WillReturn.Add("0"); //1 //3 } else if (InputPattern == "Input3") { WillReturn.Add("2"); WillReturn.Add("33 4"); WillReturn.Add("114 514"); WillReturn.Add("147"); //518 //inf } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct NimotuDef { internal int V; internal int W; } static void Main() { List<string> InputList = GetInputList(); int[] wkArr = { }; Action<string> SplitAct = pStr => wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray(); int N = int.Parse(InputList[0]); NimotuDef[] NimotuArr = new NimotuDef[N]; for (int I = 1; I <= N; I++) { SplitAct(InputList[I]); NimotuArr[I - 1].V = wkArr[0]; NimotuArr[I - 1].W = wkArr[1]; } int V = int.Parse(InputList[N + 1]); //最大の価値合計[重さ合計]なDP表 var DPDict = new Dictionary<int, int>(); DPDict[0] = 0; foreach (NimotuDef EachNimotu in NimotuArr) { foreach (int EachKey in DPDict.Keys.OrderByDescending(X => X).ToArray()) { //価値超過を枝切り if (DPDict[EachKey] > V) continue; int NewW = EachKey + EachNimotu.W; int NewV = DPDict[EachKey] + EachNimotu.V; if (DPDict.ContainsKey(NewW) && DPDict[NewW] > NewV) continue; DPDict[NewW] = NewV; } } //foreach (var EachPair in DPDict.OrderBy(X => X.Key)) { // Console.WriteLine("DPDict[{0}]={1}", EachPair.Key, EachPair.Value); //} //最小のナップサックの重さを求める int MinW = DPDict.Where(X => X.Value == V).Min(X => X.Key); if (MinW == 0) MinW = 1; Console.WriteLine(MinW); //最大のナップサックの重さを求める var Tmp = DPDict.Where(X => X.Value > V); if (Tmp.Any()) { Console.WriteLine(Tmp.Min(X => X.Key) - 1); } else { Console.WriteLine("inf"); } } }