AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。
個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。
例えば解法
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが
・なぜこの方法で上手くいくのか
・前半の動的計画法で、品物の個数を min(m[i], MAX_V) としている (できる) 理由が分からない。
誰か知恵を貸してください。
僕としてはこの解法が理解できれば満足です。
探検
データ構造,アルゴリズム,デザインパターン総合スレ 3©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
896デフォルトの名無しさん
2018/08/30(木) 11:36:30.01ID:jf9m7XuW■ このスレッドは過去ログ倉庫に格納されています
ニュース
- 【中国外務省】日中関係悪化は高市氏に責任と名指しで非難… ★5 [BFU★]
- 【インバウンド】中国からの“渡航自粛”…ツアー1000人分の直前キャンセル「キャンセル料は免除してくれ」 ことしいっぱいキャンセルに [1ゲットロボ★]
- XやChatGPTで広範囲の通信障害 投稿や閲覧できず [蚤の市★]
- 「国民の憤りを引き起こした」中国側“高市首相発言の撤回改めて要求” [どどん★]
- 【サッカー】日本代表、ボリビアに3発快勝 森保監督通算100試合目を飾る…鎌田、町野、中村がゴール [久太郎★]
- 【ローソン】ロゴの「L」で誤解生んだコーヒーカップ、デザイン変更へ 在庫使い切る3か月後にリニューアル [ぐれ★]
- 「遺体、安倍、会いたい」👈逆から読んでみて [175344491]
- 【悲報】SANA、発言撤回拒否 [769931615]
- ジャーナリストがテレビで解説「台湾問題は高市総理から言ったのではなく、立憲民主が日本の対応可能能力を暴こうとしたから」 [359572271]
- 【悲報】トランプ聖帝「高市…さん…でしたっけ?」 [878970802]
- 【悲報】タリバン、外務省のトップに土下座させる始末 [974680522]
- 山上、死刑回避し減刑か 山上母の供述で一気に酌量ムードへ [804169411]
