[今週の問題]最適な数量の組み合わせ
99 名前：大会告知の人 Easy→ ◆xc1iRlmLiw [sage]： 2008/04/20(日) 14:43:33.41 ID:0YUwfltE0 (7)
今週も忙しめなので有名問題でっ
～今週の問題～ 出典：有名問題なのでなし 難易度：やや難しい
遠くの町とかに、いろいろなものを売りにいくことにします。
商品には重さと価格が設定されていて、限界重要より合計が重くなる場合、持っていくことができません。
（等しいのはＯＫ）
また、１１個以上の同じ商品を売ることはできません。
１回で得ることのできる最高の売り上げを出力しなさい。
[入力形式]
限界重量 要素数
要素ごとの重量（要素数個）
要素ごとの価格（要素数個）
[入力例]
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
出力結果をトリップに入力！
答え確認が甘いからもしかしたら違うかも？
100 名前：大会告知の人 Hard→ ◆1mznm0BWf6 [sage]： 2008/04/20(日) 14:47:58.74 ID:0YUwfltE0 (7)
[今回の入力、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
ヒント
ナップサック問題や整数計画問題、組み合わせ最適化問題でググると幸せ！
答えはまた今度！
*4/21 線形計画法じゃないので修正。
