背包问题求解

背包问题的解法及其相关的代码 假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。

/*
 * To change this template choose Tools | Templates
 * and open the template in the editor.
 */
package Bag;

/**
 *
 * @author ZhangYu
 */
import java.util.*;

public class Bag {

    SeqStack s = new SeqStack（）;
    double temp;//零时变量，背包容量

    public void bag（int d） {
        int[] arr = new int[100];//数组

        for （int i = 0; i < 100; i++） {//体积各不相同的物品
            arr[i] = i + 1;
            // arr[i] = （int） （Math.random（） * 100）;
        }
        for （int j = 0; j < arr.length; j++） {
            if （arr[j] <= d） {
                try {
                    s.push（arr[j]）;//入栈
                } catch （Exception e） {

                    System.out.println（e.getMessage（））;
                }
                temp += arr[j];

                if （temp > d） {
                    try {
                        s.pop（）;//出栈
                    } catch （Exception e） {

                        System.out.println（e.getMessage（））;
                    }
                } else {
                    bag（d）;//递归
                }
            }

            if （d == temp） {

                System.out.println（“背包容量值为 “ + d）;
            }
        }
    }
    // if （d == temp） {

    // System.out.println（“背包容量值为 “ + d）;
    // }
                /*if （arr[i] <= d && temp == d） {

    System.out.println（d + “组成由:“）;
    }*/
    //System.out.print（“装入失败！“）;
    public static void main（String[] args） {

        int my;
        Scanner sc = new Scanner（System.in）;
        Bag b = new Bag（）;
        System.out.println（“请输入一个整数作为背包的容量：“）;
        my = sc.nextInt（）;
        b.bag（my）;
    }
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2012-06-11 17:13  背包问题Bag\
     目录           0  2012-06-11 17:13  背包问题Bag\build\
     文件        3704  2011-12-22 16:07  背包问题Bag\build.xml
     文件          92  2011-12-17 19:20  背包问题Bag\build\built-jar.properties
     目录           0  2012-06-11 17:13  背包问题Bag\build\classes\
     文件           0  2011-12-17 19:20  背包问题Bag\build\classes\.netbeans_automatic_build
     目录           0  2012-06-11 17:13  背包问题Bag\build\classes\Bag\
     文件        1768  2012-01-03 14:08  背包问题Bag\build\classes\Bag\Bag.class
     文件        1395  2012-01-03 14:08  背包问题Bag\build\classes\Bag\Bag0.class
     文件        1585  2012-01-03 14:08  背包问题Bag\build\classes\Bag\Bag1.class
     文件        1260  2012-01-03 14:08  背包问题Bag\build\classes\Bag\Bag2.class
     文件        3051  2012-01-03 14:08  背包问题Bag\build\classes\Bag\Bag3.class
     文件        2408  2012-01-03 14:08  背包问题Bag\build\classes\Bag\Bag4.class
     文件        2153  2012-01-03 14:08  背包问题Bag\build\classes\Bag\Knapsack0.class
     文件        1340  2012-01-03 14:08  背包问题Bag\build\classes\Bag\SeqStack.class
     文件         343  2012-01-03 14:08  背包问题Bag\build\classes\Bag\Stack.class
     目录           0  2012-06-11 17:13  背包问题Bag\build\classes\Date3\
     目录           0  2008-12-20 21:10  背包问题Bag\build\classes\Date3\liti\
     目录           0  2008-12-20 21:10  背包问题Bag\build\empty\
     目录           0  2012-06-11 17:13  背包问题Bag\dist\
     文件       12795  2011-12-17 19:20  背包问题Bag\dist\Bag.jar
     文件          85  2011-12-16 16:49  背包问题Bag\manifest.mf
     目录           0  2012-06-11 17:13  背包问题Bag\nbproject\
     文件       49030  2011-12-22 16:07  背包问题Bag\nbproject\build-impl.xml
     文件         475  2011-12-22 16:07  背包问题Bag\nbproject\genfiles.properties
     目录           0  2012-06-11 17:13  背包问题Bag\nbproject\private\
     文件          97  2011-12-22 16:07  背包问题Bag\nbproject\private\private.properties
     文件         211  2012-01-03 15:07  背包问题Bag\nbproject\private\private.xml
     文件        2350  2011-12-16 16:49  背包问题Bag\nbproject\project.properties
     文件         511  2011-12-16 16:49  背包问题Bag\nbproject\project.xml
     目录           0  2012-06-11 17:13  背包问题Bag\src\
............此处省略11个文件信息