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■ このスレッドは過去ログ倉庫に格納されています