频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
算法 动态规划 背包问题
2017-04-24 09:51:30         来源:Carinya的博客  
收藏   我要投稿

算法 动态规划 背包问题:给定N个物品和一个背包,物品i的质量是Wi,其价值位Vi,背包的容量为C,问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大。

在选择物品的时候,对每种物品i只有两种选择,即装入背包或不装入背包。不能将物品i装入多次,也不能只装入物品的一部分。因此,该问题被称为0-1背包问题。


分析过程

因为是0-1问题,我们需要考虑的就是第i个物品在不在背包中,设V(i, j)表示将前i(0<=i<=n)个物品之中的若干个 装入容量为j(0<=j<=C)的背包中 能得到的最大价值,先理解下面这些事实:

不装东西价值为0,V(0, j)=0 若物品i的质量Wi大于背包的质量C,那么i肯定不在背包中,V(i, 0)=0 若物品i在背包中,那么前i-1个物品的总质量一定小于等于C-Wi,V(i, j)=V(i-1, C-Wi)+Vi 若物品i的质量小于背包质量且i不在背包中,那么前i个物品的最优解必然与前i-1个的最优解相同,V(i, j)=V(i-1, j)

求解过程

稍微整理一下,可以得到0-1背包问题的状态转换方程:V(i, j)=max{V(i-1, C-Wi)+Vi,V(i-1, j)}
接下来又是一个填表的问题,java代码如下:

public class Knapsack {
    private int V[][];
    private int P[][];//记录背包中装入的物品序号
    private int n;//物品个数
    private int v[];//物品价值
    private int w[];//物品质量
    private int C;//背包容量

    private Knapsack(int[] w, int[] v, int C) {
        this.w = w;
        this.v = v;
        this.C = C;
        this.n = w.length;
        this.V = new int[n + 1][C + 1];
        this.P = new int[n + 1][C + 1];
    }

    private void print(int[][] P) {
        int i = n;
        int j = C;

        System.out.print("装入物品的序号为:");

        for (; i > 0 && j > 0; i--) {
            if (P[i][j] == 1) {
                System.out.print(i + " ");
                j -= w[i - 1];
            }
        }
    }


    private void knapsack() {

        for (int j = 0; j <= C; j++) {
            V[0][j] = 0;
        }

        for (int i = 0; i <= n; i++) {
            V[i][0] = 0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= C; j++) {
                if (w[i - 1] > j) {
                    V[i][j] = V[i - 1][j];
                } else {
                    if (V[i - 1][j - w[i - 1]] + v[i - 1] > V[i - 1][j]){
                        V[i][j] = V[i - 1][j - w[i - 1]] + v[i - 1];
                        P[i][j] = 1;//前i个点的最优解i在背包中
                    } else {
                        V[i][j] = V[i - 1][j];
                    }
                }// V[i][j] = Math.max(V[i - 1][j - w[i - 1]] + v[i - 1], V[i - 1][j]);

            }
        }

        for (int i = 0; i <= w.length; i++) {
            for (int j = 0; j <= C; j++) {
                System.out.print(V[i][j] + " ");
                if (j == C) {
                    System.out.println();
                }
            }
        }
        System.out.println("最大价值为:" + V[n][C]);
        print(P);
    }

    public static void main(String[] args) {
        int w[] = {3, 5, 2, 6, 4};
        int v[] = {4, 4, 3, 5, 3};
        int C = 12;
        Knapsack k = new Knapsack(w, v, C);
        k.knapsack();
    }
}

在真正地学了几个算法之后,我感受到看问题的方向不同,带来的视野是不同的。比如0-1背包这个问题,可以从前往后看,比如先考虑第一个物品装不装,然后第二个,第三个…就是枚举;也可以从后往前看,考虑第i个,然后建立它与前面的联系,就是状态转换方程。暂时有这么个想法,回去看下书把它总结一下。

点击复制链接 与好友分享!回本站首页
上一篇:网络接口层
下一篇:Nginx的应用场景
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站