AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。
個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。
例えば解法
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが、
前半の動的計画法は貪欲法を成功させるための処方なのか?
普通の貪欲法はナップサック問題で必ずしも最適な答えを返さないよね?
現に、貪欲法しかしないコードを提出してみたら2問ほど間違えた。
動的計画法を前処理的に用いることで貪欲法を成功させる方法って知られてるの?(それがこの解法?)
動的計画法で品物の個数を min(m[i], MAX_V) としている (できる) 理由も分からない。
他の人もほとんどこの方法で解いてるから、知られてる方法なのかと思うが調べてもヒットしない。
スレ立てるまでもない質問はここで 149匹目
■ このスレッドは過去ログ倉庫に格納されています
878デフォルトの名無しさん (オッペケ Sre7-1Rti [126.204.192.235])
2018/09/08(土) 03:07:48.41ID:vkaU9apJr■ このスレッドは過去ログ倉庫に格納されています
ニュース
- バリ島で男子生徒ら集団万引きか、防犯カメラ映像が拡散 京都の大谷中学・高校が「窃盗行為」謝罪★4 [七波羅探題★]
- 中国軍機レーダー照射、トランプ氏沈黙突く 試される日本外交 [蚤の市★]
- 【地震】青森県で震度6強 長周期地震動も 津波注意報すべて解除 ★7 [ぐれ★] [ぐれ★]
- 【広島】「万引きした人を追跡」コンビニ店員の男性(46)を果物ナイフで刺したか 中国籍の少年(17)を殺人未遂容疑で現行犯逮捕 [ぐれ★]
- トランプ大統領 エヌビディア製AI半導体の中国輸出許可 安全保障重視の方針転換 [蚤の市★]
- 【サッカー】58歳カズ「オファーが来ている」 J3福島と近日中にも交渉 早ければ年内にも決断 [征夷大将軍★]
- 【実況】博衣こよりのえちえち朝こよ🧪
- さかまた「過呼吸になった」かなた「耳聞こえない」ござる「声出ない」まつり「ご飯食べれない」
- 【悲報】高市早苗の擬人化がXで大バズりwwwwwwwwwwww [455031798]
- くそしてかがやけ
- 🎌日本の地震をお祝いします👏👏👏✨
- お茶だと思って飲んだらションベンだった
