0-1背包问题

0-1背包问题是一个典型的动态规划问题

问题背景：用有限的背包容量去装价值最多的物品的组合，物品有质量和价值。

0-1背包问题是最简单的背包问题，对于一个物品，只有两种选择——装或者不装。因此这个程序不能使用贪心算法来解，使用动态规划来解。

因为背包问题是一个动态规划问题，它可能满足动态规划的三要素。

三要素：

最优子程序、最优值，最优解

当我们有了这些算法逻辑上的准备后，就可以着手实现算法了。

算法实现

对于0-1背包问题，我们逻辑上是从上到下进行添值的，但是在算法实现的过程中，我们是使用从低往上添值的。

自上而下的算法实现

package com.dwx.passage3;

public class Knapsack {


    /*
    * n : 定义物品的数量
    * c: 定义背包的容量
    * w[]:定义我拼的重量
    * v[]:定义每个物品的价值
    * m[][]：定义记录表格*/
    private int n;
    private int c;
    private int[] w;
    private int[] v;
    private int[][] m;

    //我们写的是用来调用的方法，使用get/set方法体现我们方法的封装


    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }

    public int getC() {
        return c;
    }

    public void setC(int c) {
        this.c = c;
    }

    public int[] getW() {
        return w;
    }

    public void setW(int[] w) {
        this.w = w;
    }

    public int[] getV() {
        return v;
    }

    public void setV(int[] v) {
        this.v = v;
    }

    public int[][] getM() {
        return m;
    }

    public void setM(int[][] m) {
        this.m = m;
    }

    //算法的主体
    public void knapsack(){
        //对我们的m矩阵机型初始化
        int j,k,l;
        //对于m[][]
        //i表示是第几个物品，j表示容量为j的子背包
        for (j=0;j<=c;j++){
            //如果能够 对于子背包能够装下就装
            if (j+1 >= w[n]){
                m[n][j] = v[n];
            }
            //不能装就跳过
            else
                m[n][j] = 0;
        }

        //操作除了最后一行的其他行
        for (int i = n-1;i>=1;i--){
            for (j=0;j<=c;j++){
                if (j>=w[i]){
                    m[i][j] = m[i+1][j]>m[i+1][j-w[i]]+v[i] ?  m[i+1][j]:m[i+1][j-w[i]]+v[i];
                }
            }
        }
    }
}

测试:

import com.dwx.passage3.Knapsack;

public class KnapsackTest {
    public static void main(String[] args) {
        Knapsack knapsack = new Knapsack();
        /*
         * n : 定义物品的数量
         * c: 定义背包的容量
         * w[]:定义我拼的重量
         * v[]:定义每个物品的价值
         * m[][]：定义记录表格*/
        int c = 4;
        int n = 3;
        int w[] = new int[]{4,3,1};
        int v[] = new int[]{3000,2000,1500};
        int m[][] = new int[3][4];
        knapsack.setC(c-1);
        knapsack.setM(m);
        knapsack.setV(v);
        knapsack.setW(w);
        knapsack.setN(n-1);
        //执行方法
        knapsack.knapsack();

        //获得执行后的m表格
        //因为我们是从上到下填写的
        int[][] m1 = knapsack.getM();
        for (int[] ints : m1) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
    }
}

输出:

0	0	0	0	
0	0	0	3500	
1500	1500	1500	1500

自上而下的编写方式

Donate