實驗四 回溯算法和分支限界法 0—1背包問題

基本題二： — 1 背包問題 一、實驗目的與要求

1、掌握0—1背包問題的回溯算法；

2、進一步掌握回溯算法；

二、實驗題：

給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

三、實驗提示

template<class Typew, class Typep>

Typep Knap<Typew, Typep>::Bound(inti)

{// 計算上界

   Typew cleft = c - cw;  // 剩餘容量

   Typep b = cp;

   // 以物品機關重量價值遞減序裝入物品

   while (i<= n && w[i] <= cleft) {

      cleft -= w[i];

      b += p[i];

      i++;

      }

   // 裝滿背包

   if (i<= n) b += p[i]/w[i] * cleft;

   return b;

}

四、源代碼

importjava.util.*;

import java.io.*;

importjavax.swing.*;

importjava.lang.*;

public class SF_Beibao_01_01{

public static void main(String[] args) {

              Scanner read=new Scanner(System.in);

System.out.print("輸入背包容量：");

              int c=read.nextInt();

System.out.print("物品個數：");

              int n1=read.nextInt();

              //建構數組

              int [][]m=new int [n1][c+1];

              int []v=new int[n1];

              //數組指派及輸出

              System.out.println("物品價值數組：");

              for(inti=0;i<n1;i++){

                     v[i]=read.nextInt();

              }

              System.out.println();

              int []w=new int[n1];

              System.out.println("物品品質數組：");

                     w[i]=read.nextInt();

              knapsack(v,w,c,m);

              System.out.println("輸出0-1背包問題的最優解"+m[1][c]);

       }

    public static void knapsack(int[]v,int[]w,intc,int[][]m){

              int n=v.length-1;

              intjMax=Math.min(w[n]-1,c);

              for(int j=0;j<=jMax;j++)

              m[n][j]=0;

              for(int j=w[n];j<=c;j++)

              m[n][j]=v[n];

              for(inti=n-1;i>1;i--){

                     jMax=Math.min(w[i]-1,c);

                     for(int j=0;j<=jMax;j++)

                     m[i][j]=m[i+1][j];

                     for(int j=w[i];j<=c;j++)

                     m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

              m[1][c]=m[2][c];

              if(c>=w[1])m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);

    public static void trackback(int[][]m,int[]w,intc,int[]x){

              int n=w.length-1;

              for(inti=1;i<n;i++)

              if(m[i][c]==m[i+1][c])x[i]=0;

              else {x[i]=1;c-=w[i];}

              x[n]=(m[n][c]>0)?1:0;

    }

輸入：

背包容量：10

物品個數：5

物品價值：6 3 5 4 6

物品品質：2 2 6 5 4

結果：