練習問題

ナップサック問題

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

[入力形式]

限界重量 要素数
要素ごとの重量(要素数個)
要素ごとの価格(要素数個)

[入力例]

100 3
3 20 50
5 25 40

[出力例]

130

(3が6個、20が4個で、重量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

できるだけ面積の小さい単純多角形を出力せよ

462 名前:大会告知の人[sage] 投稿日:2008/08/03(日) 03:53:39.11 ID:C8t01WX80
久しぶりの問題投下になりますっ
今までの問題はパターンで解けない問題ばかりだったので、今回は発想勝負のNP問題に しましたっ
難しい問題だと思いますが、よかったら解いてみてくださいっ、誰も解いてくれない気がしてるけどorz
今回は答えが一意に定まらないので、コンテスト形式っぽくできたらいいなーって思ってますっ

~期限~
8/11(日) 23:59まで

~問題~ 引用:SuperCon2008本戦
n個の点の座標が与えられる。できるだけ面積の小さい単純多角形を出力せよ。
都合上、面積×2をスコアとしますっ

今回は補助ツール、入力ファイル等をつけたので、詳細はこちらからっ
結局可視化はグラフ描画ツールgnuplotに任せることにしましたorz
ttp://www8.uploader.jp/dl/vipprog/vipprog_uljp00434.rar.html

今回の問題での出力されるデータの可視化の例ですっ(スコア:3562)
out.png

トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS