01背包问题

令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数:
(1) V(i,0)=V(0,j)=0
(2) V(i,j)=V(i-1,j) j<wi
V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi
代码实现：

/**
 *@param val[] 物品价值数组
 *@param wt[]  物品重量数组 
 *@param W     背包的重量 
 */

 public static int knapsack(int val[], int wt[], int W) {

        int N = wt.length; 

        int[][] V = new int[N + 1][W + 1]; 

        for (int col = 0; col <= W; col++) {
            V[0][col] = 0;
        }
 
        for (int row = 0; row <= N; row++) {
            V[row][0] = 0;
        }
 
        for (int item=1;item<=N;item++){
            for (int weight=1;weight<=W;weight++){
                if (wt[item-1]<=weight){
                    V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
                }
                else {
                    V[item][weight]=V[item-1][weight];
                }
            }
 
        }

        for (int[] rows : V) {
            for (int col : rows) {
                System.out.format("%5d", col);
            }
            System.out.println();
        }
 
        return V[N][W];
    }