用貪心算法求解背包問題

 1   背包問題的描述：

    已知有n種物品和一個可容納M重量的背包，每種物品i的重量為 。假定将物品i的一部分 放入背包就會得到 的效益，這裡， , 。顯然，由于背包容量是M，是以，要求所有選中要裝入背包的物品總重量不得超過M.。如果這n件物品的總重量不超過M，則把所有物品裝入背包自然獲得最大效益。現需解決的問題是，這些物品重量的和大于M，該如何裝包。

2 用貪心政策求解背包問題

   首先需選出最優的量度标準。不妨先取目标函數作為量度标準，即每裝入一件物品就使背包獲得最大可能的效益值增量。在這種量度标準下的貪心方法就是按效益值的非增次序将物品一件件放到背包中去。如果正在考慮中的物品放不進去，則可隻取其一部分來裝滿背包。但這最後一次的方法可能不符合使背包每次獲得最大效益增量的量度标準，這可以換一種能獲得最大增量的物品，将它（或它的一部分）放入背包，進而使最後一次裝包也符合量度标準的要求。算法如下所示。

算法1   背包問題的貪心算法

procedure  GREEDY-KNAPSACK(P,W,M,X,n)

 //P（1：n）和W（1：n）分别含有按P（i）/W（i）≥P（i+1）/ W （i+1）排序的n件物品的效益值和重量。M是背包的容量大笑，而X（1：n）是解向量。//

                  real P(1：n)，W（1：n）,X（1：n），M，cu；

     integer  i，n;

X 0   //将解向量初始化為零

cu M  //cu是背包剩餘容量

for  i 1 to n do

    if  W(i)>cu  then  exit  endif

   X(i) 1

   cu cu-W(i)

repeat

if  i≤n  then  X(i) cu/W(i)

endif

end  GREEDY-KNAPSACK

3 具體問題

求以下情況背包問題的最優解：n=7，M=15，（ ）=（10，5，15，7，6，18，3）和（ ）=（2，3，5，7，1，4，1）。

程式清單：

package com.algorithm.knapsack;

import java.util.*;

public class GreedyKnapsack {

 public void Knapsack(double P[],double W[],int M,int n)

 { 

 int i ;

 double X[] = new double[n]; //定義結果向量

 for(i=0;i<X.length;i++)

 X[i] = 0;

 double cu = M; //cu是背包剩餘重量

 for(i=0;i<n;i++)

 { if(W[i]>cu)

 break;

     X[i] = 1;

     cu = cu-W[i];

 }

// System.out.println(i);

 if(i<n)

 X[i] = cu/W[i];

 System.out.println("問題的解為：");

 for(int k=0;k<X.length;k++)

 System.out.print(X[k] + " ");

 }

public static void main(String[] args){

 double P[] = {10,5,15,7,6,18,3}; //效益數組

 double W[] = {2,3,5,7,1,4,1};

 int M = 15,n = 7;

 double PW[] = new double[P.length];

 int[] index = new int[n];

 for(int i= 0;i<n;i++){

 PW[i] = P[i] / W[i];

 index[i] =i;

 }

 double temp =0;

     for(int i=0;i<n-1;i++)

     {

       for(int j=i+1;j<n;j++)

      {

     if(PW[i]<PW[j])       //對效益/重量數組按遞增進行排序

     {

     temp = PW[i];  

     PW[i] = PW[j];

     PW[j] = temp;

     int x=index[i];       //交換相應的數組下标

     index[i] = index[j];

      index[j] = x;               

     }

       }

     }

double[] w1 = new double[n];

double[] p1 = new double[n];

for(int i=0;i<n;i++)      

{

w1[i]=W[index[i]];     //将排序後的重量和價值數組分别賦給w1[]和p1[]

p1[i]=P[index[i]];

}

 System.out.println("各物品效益/重量的值為：");

 for(int i=0;i<n;i++)

 System.out.print(PW[i]+" ");

 System.out.println();

 System.out.println ("相應的重量數組為："+Arrays.toString(w1));  

 System.out.println ("相應的效益數組為："+Arrays.toString(p1));

 GreedyKnapsack gk = new GreedyKnapsack();

 gk.Knapsack(P,W,M,n);

 }

}