「ナップザック問題」の編集履歴（バックアップ）一覧はこちら

「ナップザック問題」(2005/11/07 (月) 05:58:44) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

<br>
<dl>
<dt>139 ：<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
：2005/10/31(月) 22:34:01</dt>
<dd><br>
[1] 授業単元： 基本プログラミング<br>
[2] 問題文(含コード&amp;リンク)：<br>
最大でmグラムまで入れることが出来る袋に以下にあげる３種類の商品を、最も高い組み合わせで入れたい。<br>

その組み合わせを出力するプログラムを作成せよ。複数組み合わせがある場合、１つ出せばよいものとする。<br>

商品a(240g\130) b(550g\335) c(850g\540)<br>
<br>
[3] 環境<br>
　[3.1] OS： windowsXP<br>
　[3.2] コンパイラ名とバージョン： 不明<br>
　[3.3] 言語： C++<br>
[4] 期限： [2005年11月2日9:00まで]<br>
[5]
その他の制限：条件分岐、繰り返し制御までしか使えません。<br>

<br>
forで全パターンを求めつつ、ifで比べて…みたいなことくらいまでは分かったのですが<br>

その先がさっぱりです…。<br>
<br></dd>
<dt>140 ：<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
：2005/10/31(月) 22:40:17</dt>
<dd>いわゆるナップサック問題<br></dd>
<dt>144 ：<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
：2005/11/01(火) 06:13:11</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/139" target=
"_blank">&gt;&gt;139</a> アルゴリズムの指示が無いので DP．<br>
<a href=
"http://ime.st/kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/1031.cpp"
target=
"_blank">http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/1031.cpp</a><br>

<br></dd>
<dt>145 ：<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
：2005/11/01(火) 06:16:38</dt>
<dd>
もし同じ商品は一度しか詰め込んではいけないなら，38行目からの<br>

if (k - w[i-1] &gt;= 0 &amp;&amp; tbl[i][k] &lt; tbl[i][k-w[i-1]] + p[i-1])
{<br>
　tbl[i][k] = tbl[i][k-w[i-1]] + p[i-1];<br>
　prev_i[i][k] = i;<br>
　prev_k[i][k] = k-w[i-1];<br>
を<br>
if (k - w[i-1] &gt;= 0 &amp;&amp; tbl[i][k] &lt; tbl[i-1][k-w[i-1]] + p[i-1])
{<br>
　tbl[i][k] = tbl[i-1][k-w[i-1]] + p[i-1];<br>
　prev_i[i][k] = i-1;<br>
　prev_k[i][k] = k-w[i-1];<br>
に変更．</dd>
</dl>