01背包问题

public class KnapsackProblem {
    public static void main(String[] args) {
        int []w={1,2,3,4,5};
        int[]value={3,4,6,8,10};
        int capacity=10;
        int n=w.length;
        ZeroOneKnapsack(w,value,n,capacity);
    }

    /**
     *
     * @param w 重量
     * @param value 价值
     * @param n 种类
     * @param capacity 容量
     */
    public static void ZeroOneKnapsack(int[]w,int[]value,int n,int capacity){
        //因为第一行均为0,所以要加1
        //第一行和第一列我们都不会用到,目的是为了更好的理解01背包
        int[][]v=new int[n+1][capacity+1];
        //因为v[0][j]和v[i][0]不处理默认为0
        //记录路径
        int [][]path=new int[n+1][capacity+1];
        for (int i = 1; i j){
                    //如果背包的容量小于当前商品的重量7
                  v[i][j]=v[i-1][j];
                }else {
                    if(v[i-1][j]0&&j>0){
            if(path[i][j]==1){
                System.out.println("商品"+i+"放入背包");
                //这里是和之前一样,我放入背包一件商品,那么我的容量也要对应的减少
                //不可能说我容量为20,容量不减少,那么就会重复
                j-=w[i-1];
            }
            i--;
        }
       /* return v[n+1][capacity];*/
    }

}

0  0  0  0  0  0  0  0  0  0  0  
0  3  3  3  3  3  3  3  3  3  3  
0  3  4  7  7  7  7  7  7  7  7  
0  3  4  7  9  10 13 13 13 13 13 
0  3  4  7  9  11 13 15 17 18 21 
0  3  4  7  9  11 13 15 17 19 21 
0  0  0  0  0  0  0  0  0  0  0  
0  1  1  1  1  1  1  1  1  1  1  
0  0  1  1  1  1  1  1  1  1  1  
0  0  0  0  1  1  1  1  1  1  1  
0  0  0  0  0  1  0  1  1  1  1  
0  0  0  0  0  0  0  0  0  1  0  
商品4放入背包
商品3放入背包
商品2放入背包
商品1放入背包
输出结果如上

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net