main.java

经典问题----背包问题的java源代码

package pacel;

import java.util.Stack;
import java.util.Scanner;

public class Main {
    

    public Main() {
    }
    

    public static void main(String[] args) {
        
        int k=10,i=0,j=0,x=0,z=0;
        int in,replace;
        String m;
        Stack have=new Stack();
        Stack bagcopy=new Stack();
        Stack bag=new Stack();
        
        Scanner scan=new Scanner(System.in);
        have.push("1");have.push("10");have.push("4");have.push("3");have.push("5");have.push("2");
        //System.out.println(""+(String)bag.peek());
       do{
            while(k!=0&i!=6){
                m=(String)have.get(i);in=Integer.valueOf(m);
                //System.out.println(""+in);
                if(in<=k){bag.push(i);k=k-in; } 
                i=i+1;
            }
                //System.out.println(""+bag.peek());
            if(k==0){
                bagcopy=(Stack) bag.clone();
                {System.out.println("next");}
                while(!bagcopy.empty()){System.out.println(""+bagcopy.pop()+";");}
                
                //System.out.println("OK"); 
                m=bag.get(0).toString();z=Integer.valueOf(m);
                m=bag.pop().toString();replace=Integer.valueOf(m);j=replace;
                m=have.get(replace).toString();replace=Integer.valueOf(m);
                k=k+replace;
                i=j+1;
                
            }
            
            else if(!bag.empty()){
                m=bag.get(0).toString();z=Integer.valueOf(m);
                m=bag.pop().toString();replace=Integer.valueOf(m);j=replace;
                m=have.get(replace).toString();replace=Integer.valueOf(m);
                k=k+replace;
                i=j+1;
            }
           
           }while(z!=5);
        
        
        

    }
    
}