问题提出

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。例如, 有3个物品，w={7, 8, 9}, v={20, 25, 30} , C=16。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

0-1背包问题物品i在考虑是否装入背包时都只有两种选择，不装入背包或装入背包，即xi ∈{𝟎,𝟏}。不能将物品i装入背包多次，也不能只装入部分的物品i。

此问题的形式化描述是：给定C>0, wi >0, vi >0,1≤i≤n,要求找出n元0-1向量（ x1, x2, …, xn ）, xi ∈{𝟎,𝟏}, 1≤i≤n,使得
图片说明

解决问题

1.最优子结构性质

设（ x1, x2, … , xn ）是所给0-1背包问题的一个最优解，
图片说明
则（ x2, … , xn ）是下面相应子问题的一个最优解：

因若不然，（ x2 ,…, xn ）不是上述子问题的一个最优解，设（ z2,…, zn ）是上述子问题的一个最优解，由此可知:

，因此：

2.建立递归关系

设所给0-1背包问题的子问题：
图片说明
最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。

举个例子：
背包物品为｛n1,n2,n3｝，
图片说明
则m(i,j)的子问题为m(i+1,j).

由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下：
图片说明

3. 递归计算最优值并构造最优解

package dynamic;

public class Knapsack_0_1 {

    private static int[] v= {20, 25, 30};
    private static int[] w= {7, 8, 9};
    private static int c=16;
    private static int n=v.length;

    public static void knapsack(int[] v,int[] w,int c,int[][] m) {
        /*
         * v[]表示物品各自的价值
         * w[]表示物品各自的重量
         * m[i][j]表示问题的最优值，即背包容量为j,可选物品为i,i+1,...,n时0-1背包的最优值
         */
        int jMax=Math.min(w[n-1]-1, c); //j的最大值为最重物品重量和背包容量的较小者(w[n]-1:为了保证下面w[n]>j)
        for(int j=0;j<=jMax;j++) //m[n][j]为最小子问题，自底向上先考虑最小子问题
            m[n][j]=0;  //这时的物品重量大于背包容量，所以价值为0（w[n]>j）
        for(int j=w[n-1];j<=c;j++) //当背包容量大于等于物品重量时，物品可以被放入背包，所以价值为物品价值
            m[n][j]=v[n-1];
        for(int i=n-1;i>1;i--) { //解决了最小子问题开始向上解决其他子问题
            jMax=Math.min(w[i-1]-1, c); //同上，找到不能放物品n的临界
            for(int j=0;j<=jMax;j++)
                m[i][j]=m[i+1][j]; //这时m[i][j]的解为子问题m[i+1][j]的解
            for(int j=w[i-1];j<=c;j++)
                m[i][j]=Math.max(m[i+1][j], v[i-1]+m[i+1][j-w[i-1]]); //当物品n可以放入背包时，要看看是物品n放进背包的价值大还是不放进背包时的价值大
        }                                                         //j-w[i]：将物品放进背包后，剩余的容量分给之前的物品（i+1）
        m[1][c]=m[2][c];  //m[1][c]为最大子问题,如果物品1的重量大于背包容量，则他的解为子问题的解
        if(c>=w[0])  //如果可以放进背包，那么看看放进背包后背包价值是否增加
            m[1][c]=Math.max(m[1][c], v[0]+m[2][c-w[0]]); 
        System.out.println("背包总价值："+m[1][c]);
    }

    public static void traceback(int[][] m,int[] w,int c,int[] x) {
        /*
         * x[]的取值为0或1，若物品i可以放进背包则x[i]=1,否则x[i]=0
         */
        for(int i=1;i<n;i++)  //从最大子问题开始求最优值
            if(m[i][c]==m[i+1][c]) x[i]=0;  //如果子问题的价值与它的子问题价值相同，说明这个物品i并没有被放进背包
            else {  //否则物品i可以被放进背包
                x[i]=1;
                c-=w[i-1];  //此时背包剩余容量就要减去物品i的重量
            }
        x[n]=(m[n][c]>0)?1:0;  //这是最小子问题，如果它的相应背包价值大于0，说明被放进了背包，否则没有
        for(int j=1;j<=n;j++) {
            System.out.print(x[j]);
        }
        System.out.println();
        for(int k=1;k<=n;k++) {
            if(x[k]==1)
                System.out.println("物品"+k+" "+"价值："+v[k-1]+" "+"重量："+w[k-1]);
        }

    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[][] m=new int[v.length+1][c+1];
        int[] x=new int[v.length+1];
        knapsack(v,w,c,m);
        traceback(m,w,c,x);

    }

}

程序截图
图片说明

演算过程
图片说明

算法复杂度分析