[[練習問題]] *ナップサック問題 [#iabfd136] -出典:有名問題なのでなし~ -難易度:やや難しい~ 遠くの町とかに、いろいろなものを売りにいくことにします。~ 商品には重さと価格が設定されていて、限界重要より合計が重くなる場合、持っていくことができません。~ (等しいのはOK)~ また、11個以上の同じ商品を売ることはできません。~ 1回で得ることのできる最高の売り上げを出力しなさい。~ 商品は正の整数単位でしか扱えません。 **[入力形式] [#r945ff69] 限界重量 要素数 要素ごとの重量(要素数個) 要素ごとの価格(要素数個) **[入力例] [#gcb2b368] 100 3 3 20 50 5 25 40 **[出力例] [#dcbdffbc] 130 (3が6個、20が4個で、重量3*6+20*4=98<=100,価格5*6+25*4=130) **[今回の問題の入力、Easy] [#wef0ee43] 100000 10 3 78 234 537 785 2345 4865 9247 21211 69867 4 82 245 523 799 2465 5023 9010 19473 46849 **[今回の入力、Hard] [#y9ae5a22] 100000 20 2 4 7 13 28 51 67 99 203 282 590 869 1037 4958 5638 7694 9304 10385 10560 16593 3 6 8 12 36 55 69 96 212 290 608 864 1033 4860 5583 7272 8674 9374 9465 13867 答え確認が甘いからもしかしたら違うかも? **答え(鳥) [#p2d85a52] Easy→ ◆xc1iRlmLiw~ Hard→ ◆1mznm0BWf6