大会告知の人の問題まとめ の履歴(No.2)

• 履歴一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 大会告知の人の問題まとめ へ行く。
  • 1 (2008-04-20 (日) 18:54:54)
  • 2 (2008-04-22 (火) 00:45:57)
  • 3 (2008-08-11 (月) 14:55:34)
  • 4 (2008-11-12 (水) 17:27:14)

練習問題

ナップサック問題†

• 出典：有名問題なのでなし
  
• 難易度：やや難しい
  

遠くの町とかに、いろいろなものを売りにいくことにします。
商品には重さと価格が設定されていて、限界重要より合計が重くなる場合、持っていくことができません。
（等しいのはＯＫ）
また、１１個以上の同じ商品を売ることはできません。
１回で得ることのできる最高の売り上げを出力しなさい。
商品は正の整数単位でしか扱えません。

[入力形式]†

限界重量　要素数
要素ごとの重量（要素数個）
要素ごとの価格（要素数個）

[入力例]†

100 3
3 20 50
5 25 40

[出力例]†

130

（３が６個、２０が４個で、重量3*6+20*4=98<=100,価格5*6+25*4=130）

[今回の問題の入力、Easy]†

100000 10
3 78 234 537 785 2345 4865 9247 21211 69867
4 82 245 523 799 2465 5023 9010 19473 46849

[今回の入力、Hard]†

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 

答え確認が甘いからもしかしたら違うかも？

答え（鳥）†

Easy→ ◆xc1iRlmLiw
Hard→ ◆1mznm0BWf6