入门博客

推荐博客1

题目

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解将那些物品装入背包可使总价值最大。

代码

package com.kevinlsui.dp;

/*
 * 动态规划：01背包问题
 * 入门博客：http://m.blog.csdn.net/article/details?id=7722810
 */
public class DpTest {

    public static void main(String[] args) {
        int m = 10;//背包总容量10
        int n = 3; //待选物品为3个
        int[] w = {3,4,5}; //三个物品的容量数组
        int[] p = {4,5,6};//三个物品的价值数组

        int[][]  c = bulidArry(m,n,w,p);//c[n][m]表示n个物品，m容量的背包最大价值
        System.out.println("最佳方案："+c[2][10]);//i下标从零开始的
        System.out.println("数组展示：");
        for(int i = 0;i<n;i++){
            for(int j = 0; j<m ; j++){
                System.out.print(c[i][j]+" ");
            }
            System.out.println();
        }

    }

    /*
     * c[n][m]表示n个物品，m容量的背包最大价值
     * 
     */
    private static int[][] bulidArry(int m, int n, int[] w, int[] p) {


        int[][] c = new int[n][m+1];//着重解释，此处必须是m+1，因为后续计算需要用到背包容量等于0时的数据,故有m+1列
        for(int k = 0;k < n;k++){
            c[k][0] = 0;
        }


        /*
         * 以下循环解释：
         * 1.只有物品1，背包的容量从0到10，分别的最大价值（后面的计算会用到）
         * 2.有物品1，物品2，背包的容量从0到10，分别的最大价值
         * 3.物品1,2,3，背包的容量从0到10，分别的最大价值
         * 其中，核心理解：
         * 对于c[i][j]的最大价值，
         * 我可以不放这物品，把资源（背包空间）留给(i-1)个物品，看下最大价值c[i-1][j]；
         * 也可以放这个物品（如果能放下），获得价值p[i],但是占用资源w[i]，留给（i-1）个物品，资源剩下(j-w[i]),此时的最大价值为 p[i]+c[i-1][j-w[i]]
         * 比较这两种方式哪一个更优
         */
        for(int i = 0;i < n ;i++){
            for(int j= 1;j < m+1;j++){//j从1开始
                if(i==0){//第一行
                    if(w[i] > j){
                        c[i][j] = 0;
                    }else{
                        c[i][j] = p[i];
                    }
                }else{//从第二行开始
                    if(w[i] > j){//放不下物品i,此时直接就是：把资源（背包空间）留给(i-1)个物品，看下最大价值c[i-1][j]
                        c[i][j] = c[i-1][j];
                    }else{//两种情况比较
                        c[i][j] = c[i-1][j] > c[i-1][j-w[i]]+p[i] ? c[i-1][j]:c[i-1][j-w[i]]+p[i];
                    }

                }

            }

        }

        return c;
    }

}

结果

最佳方案：11
数组展示：
0 0 0 4 4 4 4 4 4 4 4 
0 0 0 4 5 5 5 9 9 9 9 
0 0 0 4 5 6 6 9 10 11 11