C/C++の宿題のまとめ@Wiki
ナップザック問題
最終更新:
匿名ユーザー
-
view
- 139 :デフォルトの名無しさん :2005/10/31(月) 22:34:01
[1] 授業単元: 基本プログラミング
[2] 問題文(含コード&リンク):
最大でmグラムまで入れることが出来る袋に以下にあげる3種類の商品を、最も高い組み合わせで入れたい。
その組み合わせを出力するプログラムを作成せよ。複数組み合わせがある場合、1つ出せばよいものとする。
商品a(240g\130) b(550g\335) c(850g\540)
[3] 環境
[3.1] OS: windowsXP
[3.2] コンパイラ名とバージョン: 不明
[3.3] 言語: C++
[4] 期限: [2005年11月2日9:00まで]
[5] その他の制限:条件分岐、繰り返し制御までしか使えません。
forで全パターンを求めつつ、ifで比べて…みたいなことくらいまでは分かったのですが
その先がさっぱりです…。
- 140 :デフォルトの名無しさん :2005/10/31(月) 22:40:17
- いわゆるナップサック問題
- 144 :デフォルトの名無しさん :2005/11/01(火) 06:13:11
- >>139 アルゴリズムの指示が無いので DP.
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/1031.cpp
- 145 :デフォルトの名無しさん :2005/11/01(火) 06:16:38
-
もし同じ商品は一度しか詰め込んではいけないなら,38行目からの
if (k - w[i-1] >= 0 && tbl[i][k] < tbl[i][k-w[i-1]] + p[i-1]) {
tbl[i][k] = tbl[i][k-w[i-1]] + p[i-1];
prev_i[i][k] = i;
prev_k[i][k] = k-w[i-1];
を
if (k - w[i-1] >= 0 && tbl[i][k] < tbl[i-1][k-w[i-1]] + p[i-1]) {
tbl[i][k] = tbl[i-1][k-w[i-1]] + p[i-1];
prev_i[i][k] = i-1;
prev_k[i][k] = k-w[i-1];
に変更.