search.java

算法中一个经典问题：背包问题的优先队列算法实现。

public class search {
    int iLeavingw[];
    lcQueue lc,end;
    int maxweigh,maxvalue;
    int weightemp,valuetemp;
    node[] data;
    resultNode H;
    int path[];


    public search(node[] data_,int maxweigh_) {
        data=data_;weightemp=valuetemp=maxvalue=0;
        maxweigh=maxweigh_;
        lc=new lcQueue();
        lc.flag=2;
     //   lc.next=null;
        end=new lcQueue();
        end.flag=2;
        end.next=null;
        lc.next=end;
        iLeavingw=new int[data_.length];
        H=new resultNode();
        H.parent=null;
        H.flag=2;

        path=new int[data_.length];
    }

    public resultNode best()
    {
        iLeavingw[data.length-1]=0;
        for(int i=data.length-2;i>=0;i--)
            iLeavingw[i]=iLeavingw[i+1]+data[i+1].value;
        int count=0;
        lcQueue E=new lcQueue();
  //      H.parent=null;

        while(count<data.length)
        {
            if(weightemp+data[count].weigh<=maxweigh)
            {

                lcQueue insertData=new lcQueue();
         //       valuetemp+=data[count].value;
         //       weightemp+=data[count].weigh;

                if(valuetemp+data[count].value>maxvalue)
                maxvalue=valuetemp+data[count].value;
                System.out.println("$$valuetemp-----:"+valuetemp);
                System.out.println("$$maxvalue-------:"+maxvalue);

                insertData.id=data[count].id;
                insertData.sumweigh=weightemp+data[count].weigh;
                insertData.flag=1;
                insertData.next=null;
                insertData.pri=valuetemp+iLeavingw[count]+data[count].value;
         //       insertData.pri=weightemp+data[count].weigh;
                insertData.sumvalue=valuetemp+data[count].value;

                resultNode newnode=new resultNode();
                newnode.id=insertData.id;
                newnode.flag=1;
                newnode.parent=H;

                insertData.ptr=newnode;

                addToQueue(insertData,count,1);//调整队列
        //        System.out.print("(id:"+insertData.id+",flag:"+insertData.flag+",value:"+insertData.sumvalue+")");

            }




            if(bound(count,valuetemp,maxvalue))
     //       if(valuetemp+iLeavingw[count]<maxvalue)
            {
                lcQueue insert = new lcQueue();
                insert.id=data[count].id;
                insert.flag=0;
                insert.next=null;
                insert.pri=valuetemp+iLeavingw[count];
                insert.sumvalue=valuetemp;
                insert.sumweigh=weightemp;

                resultNode newnode=new resultNode();
                newnode.id=insert.id;
                newnode.flag=0;
                newnode.parent=H;

                insert.ptr=newnode;

                addToQueue(insert,count,0);
           //     System.out.print("(id:"+insert.id+",flag:"+insert.flag+")");

            }

            E=deleteQueue();
            if(E==null)
                break;
            valuetemp=E.sumvalue;
     //       valuetemp=E.pri-iLeavingw[count];
            weightemp=E.sumweigh;
            H=E.ptr;
            int s=H.id+1;
            System.out.println(s+","+E.flag);
            count=E.id+1;
     //       System.out.print("(id:"+E.id+",flag:"+E.flag+",weigh:"+E.sumweigh+",value:"+E.sumvalue+")");
        }
   //     System.out.println("***********************************");
        int w=0,v=0;
        for(int bk=data.length-1;bk>=count;bk--)
            System.out.println(bk+"processing$$$ H pointer:"+bk+",flag:"+0);
        for(int k=count-1;H.flag!=2 && k>=0;H=H.parent)
        {
            System.out.print(H.id+",");

            if(H.flag==1)
            {
                w+=data[k].weigh;
                v+=data[k].value;
                path[k]=1;
            }
          System.out.println("processing$$$ H pointer:" + H.id + ",falg:" + H.flag);
            k--;
        }
        System.out.println(w+","+v);

        return H;

    }

    public void addToQueue(lcQueue idata,int count,int flag_)
    {
        lcQueue p=lc.next,q=lc;
        int head=1;
        if(p==end)
        {
            lc.next = idata;
            idata.next=end;
        }
        else
        {
            while (p.pri >= idata.pri && p.next!=end) {
                q = p;
                p = p.next;
                head++;
            }

           if(p.next==end && p.pri>idata.pri)
           {
             idata.next = p.next;
             p.next = idata;
           }

  //          if ((p.next==end && p.pri<idata.pri && q.flag==2) || p.next!=end)
           else
           {
                idata.next = p;
                q.next = idata;
            }

        }
    }

    public lcQueue deleteQueue()
    {

        lcQueue del;
        del=lc.next;
        if(del==end)
            return null;
        lc.next=del.next;
        return del;
    }

    public boolean bound(int k,int value_,int max)
    {
        int b=k;
        for(int i=k+1;i<data.length;i++)
            value_ += data[i].value;

        if(value_<=max)
            return false;
        else return true;
    }

    public void result()
    {
        int k=data.length-1;
        System.out.print("the result:");
        int v=0,w=0;
       for(resultNode p=H;p!=null && k>=0;p=p.parent)
        {

                if(p.flag==1)
                {
                    v+=data[k].value;
                    w+=data[k].weigh;
                    path[k]=1;
                }
                k--;

                System.out.print("(id:"+p.id+",flag:"+p.flag+")<-");
                    System.out.println(p.id+",");
        }

         resultNode p=H;
  //      System.out.print("-------H.id:"+best().id+",H.flag:"+best().flag);
        for(k=data.length-1;k>=0 && p!=null;k--)
        {
           path[k] = p.flag;
            p=p.parent;
            System.out.print(path[k]);
        }
        System.out.println("$$$$$weigh,"+w+"value:"+v);
    }
}