https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E3%83%8A%E3%83%83%E3%83%97%E3%82%B6%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C
ナップザック問題 - 版の履歴
2026-04-09T14:45:20Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%8A%E3%83%83%E3%83%97%E3%82%B6%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C&diff=10823&oldid=prev
2008年11月13日 (木) 04:22にAlbeit-Kunによる
2008-11-13T04:22:59Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年11月13日 (木) 04:22時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >7行目:</td>
<td colspan="2" class="diff-lineno">7行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></table></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></table></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:組合せ最適化|なっぷさっくもんだい]]</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[category:近似・知能・感覚的手法|なっぷさっくもんだい]]</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:グラフ･ネットワーク|なっぷさっくもんだい]]</ins></div></td></tr>
</table>
Albeit-Kun
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%8A%E3%83%83%E3%83%97%E3%82%B6%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C&diff=6635&oldid=prev
Orsjwiki: "ナップサック問題" を保護しました。 [edit=sysop:move=sysop]
2007-07-20T01:16:31Z
<p>"ナップサック問題" を保護しました。 [edit=sysop:move=sysop]</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<tr class="diff-title" lang="ja">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2007年7月20日 (金) 01:16時点における版</td>
</tr><tr><td colspan="2" class="diff-notice" lang="ja"><div class="mw-diff-empty">(相違点なし)</div>
</td></tr></table>
Orsjwiki
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%8A%E3%83%83%E3%83%97%E3%82%B6%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C&diff=5450&oldid=prev
2007年7月17日 (火) 07:22に122.17.2.240による
2007-07-17T07:22:17Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月17日 (火) 07:22時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>【なっぷさっくもんだい (knapsack problem)】</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''</ins>【なっぷさっくもんだい (knapsack problem)】<ins class="diffchange diffchange-inline">'''</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br></div></td></tr>
</table>
122.17.2.240
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%8A%E3%83%83%E3%83%97%E3%82%B6%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C&diff=4260&oldid=prev
2007年7月13日 (金) 04:43に211.9.146.171による
2007-07-13T04:43:00Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月13日 (金) 04:43時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >2行目:</td>
<td colspan="2" class="diff-lineno">2行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><table></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><table <ins class="diffchange diffchange-inline">align = center</ins>></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> <tr><td>目的関数 </td> <td><math>\sum_{i=1}^{n} c_{i}x_{i} \to \,</math>最大化</td></tr></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> <tr><td>目的関数 </td> <td><math>\sum_{i=1}^{n} c_{i}x_{i} \to \,</math>最大化</td></tr></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> <tr><td>制約条件 </td> <td><math>\sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,</math>：非負整数</td></tr></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> <tr><td>制約条件 </td> <td><math>\sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,</math>：非負整数</td></tr></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></table></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></table></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.</div></td></tr>
</table>
211.9.146.171
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%8A%E3%83%83%E3%83%97%E3%82%B6%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C&diff=3904&oldid=prev
2007年7月12日 (木) 19:39に211.9.162.254による
2007-07-12T19:39:02Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月12日 (木) 19:39時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>【なっぷさっくもんだい (knapsack problem)】</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>【なっぷさっくもんだい (knapsack problem)】</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. </div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <ins class="diffchange diffchange-inline"><br></ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\begin{center}</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><table></ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\begin{tabular}{ll}</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <tr><td>目的関数 </td> <td><math></ins>\sum_{i=1}^<ins class="diffchange diffchange-inline">{</ins>n} <ins class="diffchange diffchange-inline">c_{i}x_{i} </ins>\to \<ins class="diffchange diffchange-inline">,</math></ins>最大化<ins class="diffchange diffchange-inline"></td></tr></ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">目的関数 & $\displaystyle{</del>\sum_{i=1}^n <del class="diffchange diffchange-inline">\: c_ix_i </del>}<del class="diffchange diffchange-inline">\; </del>\to \<del class="diffchange diffchange-inline">; </del>最大化 <del class="diffchange diffchange-inline">$\\</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <tr><td>制約条件 </td> <td><math></ins>\sum_{i=1}^<ins class="diffchange diffchange-inline">{</ins>n<ins class="diffchange diffchange-inline">} a_{i}x_{i</ins>} \leq b,x_i\<ins class="diffchange diffchange-inline">,</math>：非負整数</td></tr></ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">制約条件 & $\displaystyle{</del>\sum_{i=1}^n <del class="diffchange diffchange-inline">\: a_ix_i </del>}\leq b,<del class="diffchange diffchange-inline">\; </del>x_i<del class="diffchange diffchange-inline">:</del>\<del class="diffchange diffchange-inline">;$非負整数</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></table></ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\end{tabular}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\end{center}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.</div></td></tr>
</table>
211.9.162.254
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%8A%E3%83%83%E3%83%97%E3%82%B6%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C&diff=3866&oldid=prev
2007年7月12日 (木) 17:41に211.9.162.254による
2007-07-12T17:41:10Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月12日 (木) 17:41時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>【なっぷさっくもんだい (knapsack problem)】</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>【なっぷさっくもんだい (knapsack problem)】</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>重さが<del class="diffchange diffchange-inline">$</del>a_i<del class="diffchange diffchange-inline">$</del>の物品<del class="diffchange diffchange-inline">$</del>i<del class="diffchange diffchange-inline">$</del>をナップサックに詰めるとき, 重量制限 <del class="diffchange diffchange-inline">$</del>b<del class="diffchange diffchange-inline">$ </del>の下で価値 <del class="diffchange diffchange-inline">$</del>c_i<del class="diffchange diffchange-inline">$ </del>の総和が最大になるものを選ぶという次の整数計画問題. </div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>重さが<ins class="diffchange diffchange-inline"><math></ins>a_i<ins class="diffchange diffchange-inline">\,</math></ins>の物品<ins class="diffchange diffchange-inline"><math></ins>i<ins class="diffchange diffchange-inline">\,</math></ins>をナップサックに詰めるとき, 重量制限 <ins class="diffchange diffchange-inline"><math></ins>b<ins class="diffchange diffchange-inline">\,</math> </ins>の下で価値 <ins class="diffchange diffchange-inline"><math></ins>c_i<ins class="diffchange diffchange-inline">\,</math> </ins>の総和が最大になるものを選ぶという次の整数計画問題. </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\begin{center}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\begin{center}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\begin{tabular}{ll}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\begin{tabular}{ll}</div></td></tr>
</table>
211.9.162.254
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%8A%E3%83%83%E3%83%97%E3%82%B6%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C&diff=3563&oldid=prev
122.17.2.240: 新しいページ: '【なっぷさっくもんだい (knapsack problem)】 重さが$a_i$の物品$i$をナップサックに詰めるとき, 重量制限 $b$ の下で価値 $c_i$ の総和が...'
2007-07-12T14:42:53Z
<p>新しいページ: '【なっぷさっくもんだい (knapsack problem)】 重さが$a_i$の物品$i$をナップサックに詰めるとき, 重量制限 $b$ の下で価値 $c_i$ の総和が...'</p>
<p><b>新規ページ</b></p><div>【なっぷさっくもんだい (knapsack problem)】<br />
<br />
重さが$a_i$の物品$i$をナップサックに詰めるとき, 重量制限 $b$ の下で価値 $c_i$ の総和が最大になるものを選ぶという次の整数計画問題. <br />
\begin{center}<br />
\begin{tabular}{ll}<br />
目的関数 & $\displaystyle{\sum_{i=1}^n \: c_ix_i }\; \to \; 最大化 $\\<br />
制約条件 & $\displaystyle{\sum_{i=1}^n \: a_ix_i }\leq b,\; x_i:\;$非負整数<br />
\end{tabular}<br />
\end{center}<br />
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.</div>
122.17.2.240