knapsackproblem.htm

“常见程式演算”主要收集一些常见的程式练习题目

      <td align="left" valign="top"><small>０ </small></td>

    </tr>

  
  </tbody>
</table>


<ul>
  <li> 放入橘子
  </li>
</ul>

<table border="1" width="50%">

  <tbody>

    <tr>

      <td align="left" valign="top"><small>背包负重 </small></td>

      <td align="left" valign="top"><small>1 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>4 </small></td>

      <td align="left" valign="top"><small>5 </small></td>

      <td align="left" valign="top"><small>6 </small></td>

      <td align="left" valign="top"><small>7 </small></td>

      <td align="left" valign="top"><small>8 </small></td>

    </tr>

    <tr>

      <td align="left" valign="top"><small>value </small></td>

      <td align="left" valign="top"><small>０ </small></td>

      <td align="left" valign="top"><small>2250 </small></td>

      <td align="left" valign="top"><small>2250 </small></td>

      <td align="left" valign="top"><small>4500 </small></td>

      <td align="left" valign="top"><small>5700 </small></td>

      <td align="left" valign="top"><small>6750 </small></td>

      <td align="left" valign="top"><small>7950 </small></td>

      <td align="left" valign="top"><small>9000 </small></td>

    </tr>

    <tr>

      <td align="left" valign="top"><small>item </small></td>

      <td align="left" valign="top"><small>－ </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>０ </small></td>

      <td align="left" valign="top"><small>1 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>０ </small></td>

    </tr>

  
  </tbody>
</table>

<br>

<ul>
  <li> 放入草莓
  </li>
</ul>

<table border="1" width="50%">

  <tbody>

    <tr>

      <td align="left" valign="top"><small>背包负重 </small></td>

      <td align="left" valign="top"><small>1 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>4 </small></td>

      <td align="left" valign="top"><small>5 </small></td>

      <td align="left" valign="top"><small>6 </small></td>

      <td align="left" valign="top"><small>7 </small></td>

      <td align="left" valign="top"><small>8 </small></td>

    </tr>

    <tr>

      <td align="left" valign="top"><small>value </small></td>

      <td align="left" valign="top"><small>1100 </small></td>

      <td align="left" valign="top"><small>2250 </small></td>

      <td align="left" valign="top"><small>3350 </small></td>

      <td align="left" valign="top"><small>4500 </small></td>

      <td align="left" valign="top"><small>5700 </small></td>

      <td align="left" valign="top"><small>6800 </small></td>

      <td align="left" valign="top"><small>7950 </small></td>

      <td align="left" valign="top"><small>9050 </small></td>

    </tr>

    <tr>

      <td align="left" valign="top"><small>item </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>０ </small></td>

      <td align="left" valign="top"><small>1 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

    </tr>

  
  </tbody>
</table>

<br>

<ul>
  <li> 放入甜瓜
  </li>
</ul>

<table border="1" width="50%">

  <tbody>

    <tr>

      <td align="left" valign="top"><small>背包负重 </small></td>

      <td align="left" valign="top"><small>1 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>4 </small></td>

      <td align="left" valign="top"><small>5 </small></td>

      <td align="left" valign="top"><small>6 </small></td>

      <td align="left" valign="top"><small>7 </small></td>

      <td align="left" valign="top"><small>8 </small></td>

    </tr>

    <tr>

      <td align="left" valign="top"><small>value </small></td>

      <td align="left" valign="top"><small>1100 </small></td>

      <td align="left" valign="top"><small>2250 </small></td>

      <td align="left" valign="top"><small>3350 </small></td>

      <td align="left" valign="top"><small>4500 </small></td>

      <td align="left" valign="top"><small>5700 </small></td>

      <td align="left" valign="top"><small>6800 </small></td>

      <td align="left" valign="top"><small>7950 </small></td>

      <td align="left" valign="top"><small>9050 </small></td>

    </tr>

    <tr>

      <td align="left" valign="top"><small>item </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>０ </small></td>

      <td align="left" valign="top"><small>1 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

      <td align="left" valign="top"><small>2 </small></td>

      <td align="left" valign="top"><small>3 </small></td>

    </tr>

  
  </tbody>
</table>

<br>
由最后一个表格，可以得知在背包负重8公斤时，最多可以装入9050元的水果，而最后一个装入的
水果是3号，也就是草莓，装入了草莓，背包只能再放入7公斤（8-1）的水果，所以必须看背包负重7公斤时的最佳解，最后一个放入的是2号，也就
是橘子，现在背包剩下负重量5公斤（7-2），所以看负重5公斤的最佳解，最后放入的是1号，也就是苹果，此时背包负重量剩下0公斤（5-5），无法
再放入水果，所以求出最佳解为放入草莓、橘子与苹果，而总价为9050元。<br>
<br>
<h2> 实作</h2>

<ul>
  <li> C
  </li>
</ul>

<pre>#include &lt;stdio.h&gt; <br>#include &lt;stdlib.h&gt; <br><br>#define LIMIT 8   // 重量限制 <br>#define N 5       // 物品种类 <br>#define MIN 1     // 最小重量 <br><br>struct body { <br>    char name[20]; <br>    int size; <br>    int price; <br>}; <br><br>typedef struct body object; <br><br>int main(void) { <br>    int item[LIMIT+1] = {0}; <br>    int value[LIMIT+1] = {0}; <br>    int newvalue, i, s, p; <br><br>    object a[] = {{"李子", 4, 4500}, <br>                  {"苹果", 5, 5700}, <br>                  {"橘子", 2, 2250}, <br>                  {"草莓", 1, 1100}, <br>                  {"甜瓜", 6, 6700}}; <br><br>    for(i = 0; i &lt; N; i++) { <br>        for(s = a[i].size; s &lt;= LIMIT; s++) { <br>            p = s - a[i].size; <br>            newvalue = value[p] + a[i].price; <br>            if(newvalue &gt; value[s]) {// 找到阶段最佳解 <br>                value[s] = newvalue; <br>                item[s] = i; <br>            } <br>        } <br>    } <br><br>    printf("物品\t价格\n"); <br>    for(i = LIMIT; i &gt;= MIN; i = i - a[item[i]].size) { <br>        printf("%s\t%d\n", <br>                  a[item[i]].name, a[item[i]].price); <br>    } <br><br>    printf("合计\t%d\n", value[LIMIT]); <br><br>    return 0; <br>}  <br></pre>

<br>

<ul>
  <li> Java
  </li>
</ul>

<pre>class Fruit {<br>    private String name;<br>    private int size;<br>    private int price;<br>    <br>    public Fruit(String name, int size, int price) {<br>        this.name = name;<br>        this.size = size;<br>        this.price = price;<br>    }<br>    <br>    public String getName() {<br>        return name;<br>    }<br><br>    public int getPrice() {<br>        return price;<br>    }<br><br>    public int getSize() {<br>        return size;<br>    }<br>}<br><br>public class Knapsack {<br>    public static void main(String[] args) {<br>        final int MAX = 8;<br>        final int MIN = 1;<br>        int[] item = new int[MAX+1]; <br>        int[] value = new int[MAX+1];  <br><br>        Fruit fruits[] = {<br>                new Fruit("李子", 4, 4500), <br>                new Fruit("苹果", 5, 5700), <br>                new Fruit("橘子", 2, 2250), <br>                new Fruit("草莓", 1, 1100), <br>                new Fruit("甜瓜", 6, 6700)}; <br><br>        for(int i = 0; i &lt; fruits.length; i++) { <br>            for(int s = fruits[i].getSize(); s &lt;= MAX; s++) { <br>                int p = s - fruits[i].getSize(); <br>                int newvalue = value[p] + <br>                                   fruits[i].getPrice(); <br>                if(newvalue &gt; value[s]) {// 找到阶段最佳解 <br>                    value[s] = newvalue; <br>                    item[s] = i; <br>                } <br>            } <br>        } <br><br>        System.out.println("物品\t价格"); <br>        for(int i = MAX; <br>            i &gt;= MIN; <br>            i = i - fruits[item[i]].getSize()) { <br>            System.out.println(fruits[item[i]].getName()+ <br>                    "\t" + fruits[item[i]].getPrice()); <br>        } <br><br>        System.out.println("合计\t" + value[MAX]);  <br>    }<br>}</pre>
<br>
<br>
<br>



</body>
</html>