0/1背包问题与动态规划

时间:2021-12-15 18:40:23

假设背包容量M=9;(P1,P2,P3,P4,P5,P6)=(15,18,40,56,30,10);(W1,W2,W3,W4,W,5,W6)=(3,2,5,8,5,1)。

算法思想

   变量解释:
  F(i):Si中第一对序偶在数组中的位置(下标)
  l, h:Si-1的第一对序偶和最后一对序偶在数组中的位置,即F(i-1)和F(i)-1.
  k: Si-1中当前要加入Si的序偶的位置.
  u: 在Si-1能够产生Si1序偶的最后一个位置,即对于u+1<=v<= h的序偶(Pv,Wv),有Wv+wi>M.
  j: 当前正在生成Si1的Si-1中序偶的位置.
  next: Si中要加入序偶的位置.

1.初始化

   最初只有S0的信息,F(0),P(1),W(1),l,h,F(1),next

2.生成Si

   (1)逐一生成Si1中的序偶(pp,ww)

        在未处理的Si-1中:  a. 重量比ww小的序偶(P(k),W(k))加入Si中判断(pp,ww)是否被支配,是否可放入Si中;

                  b. 如(pp,ww)可放入Si中,重量比ww大的序偶,如被(pp,ww) 支配则舍弃,不放入Si中。

   (2) Si1中的序偶逐一生成且判断是否放入Si中后,Si-1中若还有序偶没有加入Si中,则全部加入;

3.生成最末序偶,回溯构造最优决策序列

 

 

序偶:

  支配规则: 如果Si-1 和 Si1 中一个有(Pj,Wj), 另一个有(Pk,Wk), 并且在Wj>=Wk的同时有Pj<=Pk,  那么, 序偶(Pj,Wj)被放弃

 
  Si的序偶的生成

    每生成Si1中的一个序偶(pp,ww),考察哪些序偶要被加入到Si

    ①将Si-1中W<ww的序偶加入Si

    ②由支配规则看(pp,ww)是否加入Si,考察Si-1中W<ww的最后一个序偶(Pg,Wg),若Pg≥pp,则舍弃(pp,ww)

  否则

    ③ 考察Si-1中下一个序偶(pg+1, Wg+1),若Wg+1= ww,则pp¬max{pg+1,pp}

    ④ (pp,ww)->Si

    ⑤考察Si-1中W>ww的序偶有无被(pp,ww)支配,若被支配则舍弃

0/1背包问题与动态规划0/1背包问题与动态规划
  1 package dynamicProgramming;
  2 
  3 public class DKNAP {
  4     double M;
  5     double[] P,W;
  6     int n=6;
  7     int[] X=new int[n+1];
  8     DKNAP(){
  9         M=9;
 10         double[] temp0={0,15,18,40,56,30,10};//本程序P,W以下标从1开始计数
 11         P=temp0;
 12         double[] temp1={0,3,2,5,8,5,1};
 13         W=temp1;
 14         X=dknap(P,W,M,X,n);
 15         System.out.println();
 16         double sum=0;
 17         System.out.print("X[n]:");
 18         for(int i=1;i<=n;i++){
 19             sum+=X[i]*P[i];
 20             System.out.print(X[i]+" ");
 21         }
 22         System.out.println("sum="+sum);
 23     }
 24     public int[] dknap(double[] p,double[] w,double M,int[] X,int n){
 25         int[] F=new int[n+1];
 26         int m=100;
 27         double[] P=new double[m];
 28         double[] W=new double[m];
 29         double pp,ww;
 30         int l,h,i,j,k,next,u,v;
 31         F[0]=1;
 32         P[1]=W[1]=0;//S0
 33         System.out.println("S0:");
 34         System.out.print("("+P[1]+","+W[1]+")");
 35         l=h=1;//s0的起始和结束位置
 36         F[1]=next=2;//P和W的第一个空位
 37         for(i=1;i<n;i++){//生成Si  1~n-1
 38             k=l;
 39             for(v=F[i-1];v<F[i];v++){
 40                 if(W[v]+w[i]>M)
 41                     break;
 42             }
 43             u=v-1;//在l<=r<=h中使W(v)+W[i]<=M的最大的v;
 44             System.out.println();
 45             System.out.println("u:"+u+" (P[u],W[u]):("+P[u]+","+W[u]+")"+" w[i]:"+w[i]);
 46             System.out.println("S"+i+":");
 47             for(j=l;j<=u;j++){//生成Si,1及归并
 48                 pp=P[j]+p[i];
 49                 ww=W[j]+w[i];//Si,i的下一个元素
 50                 while (k<=h&&W[k]<ww){//从Si-1中取元素来归并
 51                     P[next]=P[k];
 52                     W[next]=W[k];
 53                     System.out.print("("+P[k]+','+W[k]+") ");
 54                     next++;
 55                     k++;
 56                 }
 57                 if(k<=h&&W[k]==ww){//
 58                     pp=max(pp,P[k]);
 59                     k++;
 60                 }
 61                 if(pp>P[next-1]){//Si-1中最后一个序偶(P[next-1],W[next-1]),如果P[next-1]>=pp,则舍弃(pp,ww)
 62                     P[next]=pp;
 63                     W[next]=ww;
 64                     next++;
 65                     System.out.print("("+pp+','+ww+") ");
 66                 }
 67                 while(k<=h&&P[k]<=P[next-1]){//清除
 68                     k++;
 69                 }
 70             }
 71                 //将Si-1中剩余元素并入Si//
 72                 while(k<=h){
 73                     P[next]=P[k];
 74                     W[next]=W[k];
 75                     System.out.print("("+P[k]+','+W[k]+") ");
 76                     next++;
 77                     k++;
 78                 }
 79                 //对Si+1置初值//
 80                 l=h+1;
 81                 h=next-1;
 82                 F[i+1]=next;    
 83         }
 84         double Px=P[next-1];
 85         double Wx=W[next-1];
 86         double Wl=0;
 87         double Pl=0;
 88         for(i=F[n-1];i<F[n]&&W[i]+w[n]<M;i++){
 89             if(W[i]>Wl){
 90                 Wl=W[i];
 91                 Pl=P[i];
 92             }
 93         }
 94         double Py=Pl+p[n];
 95         double Wy=Wl+w[n];
 96         if(Px>Py){
 97             X[n]=0;
 98             
 99         }
100         else{
101             X[n]=1;
102             Px=Pl;
103             Wx=Wl;
104         }
105         for(k=n-1;k>0;k--){
106         boolean flag=false;
107         for(i=F[k-1];i<F[k];i++){
108             if(P[i]==Px&&W[i]==Wx){
109                 flag=true;
110                 break;
111             }
112         }
113         if(!flag){
114             X[k]=1;
115             Px=Px-p[k];
116             Wx=Wx-w[k];
117         }
118         }
119         return X;
120     }
121     public double max(double a,double b){
122         if(a>=b)
123             return a;
124         else
125             return b;
126     }
127     public static void main(String[] args) {
128         // TODO Auto-generated method stub
129         new DKNAP();
130     }
131 
132 }
View Code

 

测试结果:
0/1背包问题与动态规划