背包问题---物体不可分割的装载问题---0-1背包问题

• 问题

在宝物不可分割的情况下， 即0-1背包问题， 已经不具有贪心选择性质，原问题的整体最优解无法通过一系列局部最优的选择得到，因此这类问题得到的是近似解。

给定 n 种宝物和一个容量为 m的背包，第i件宝物的重量是w[i]，价值是v[i]。

问：应该如何选择装入背包的宝物，使得装入背包中的宝物的总价值最大？

• 思路

面对每个宝物，我们只有选择拿取或者不拿两种选择，不能选择装入某宝物的一部分，也不能装入同一宝物多次。

一位网友的思路：https://blog.****.net/xp731574722/article/details/70766804

【解决办法：声明一个 大小为  dp[n][m] 的二维数组，dp[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为  j 时所能获得的最大价值 ，那么我们可以很容易分析得出 dp[i][j] 的计算方法，

（1）. j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿

dp[ i ][ j ] = dp[ i-1 ][ j ]

（2）. j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。

如果拿取，dp[ i ][ j ]=dp[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的dp[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。

如果不拿，dp[ i ][ j ] = dp[ i-1 ][ j ] , 同（1）

究竟是拿还是不拿，自然是比较这两种情况那种价值最大。】

代码实现：

package com.algorithm;

import java.util.Scanner;

class Treasure1 {
    private int w;//每个宝物的重量
    private int v;//每个宝物的价值

    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 class BookTest01 {
    public static void main(String[] args) {
        System.out.println("请输入宝物的数量n及背包的容量m");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//宝物的种类
        int m = sc.nextInt();//背包的重量
        System.out.println("请输入每个宝物的重量和价值，用空格分开");
        Treasure1[] tre = new Treasure1[n + 1];
        for (int i = 1; i <= n; i++) {
            tre[i] = new Treasure1();
            tre[i].setW(sc.nextInt());
            tre[i].setV(sc.nextInt());
        }
        int[][] dp = new int[n + 1][m + 1];
        //构成动态规划表
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {

                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                    continue;
                }

                if (i == 1) {
                    if (j < tre[i].getW())
                        dp[i][j] = 0;
                    else
                        dp[i][j] = tre[i].getV();
                } else {
                    if (j < tre[i].getW()) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j - tre[i].getW()] + tre[i].getV(), dp[i - 1][j]);
                    }
                }
            }

        }

        System.out.println("输出动态规划表如下");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }

        int r = n;
        int s = m;
        int allSolu = dp[r][s];
        //寻找哪些物品放入背包
        while (allSolu >= 0) {
            if (m > 0 && dp[r][s] == dp[r - 1][s]) {
                r = r - 1;
            } else {
                System.out.println("重为" + tre[r].getW() + " 价值为" + tre[r].getV() + "加入背包");
                r = r - 1;
                if (r == 0) {
                    return;
                } else {
                    s = s - tre[n].getW();
                    allSolu = allSolu - tre[r].getW();
                }
            }
        }
    }
}

• 结果：

​​​​​​​