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];
に変更.
人気記事ランキング
目安箱バナー