【动态规划】0-1背包问题

题目:现在有四个物品，背包总容量为8，背包最多能装入价值为多少的物品?

我的图解

表格a【i】【j】表示的是容量为j的背包装入前i个物品的最大价值。

拿a【1】【1】来说，它的值就是背包容量为1，只考虑编号0，1的物品时，背包所能装入的最大价值；

然后既然是动态规划，那就一定有初值，也就是a【0】【j】 = 0; a【i】【0】 = 0;即第一行和第一列都为0；

然后根据初值来推后面的值；

首先要判断本行所对应的物品是否能装入背包，

拿a【1】【1】来说，首先要判断，若只考虑编号为1的物品，它是否可以装入背包，此时的背包容量为1，而编号为1的物品的体积为2，故它无法装入背包，那么a【1】【1】的值和背包容量为1，只考虑编号为0的物品时，背包所能装入的最大价值(即a【0】【1】)是相等的；

若能装入背包；那么有两种选择:

(1)装入本行物品，即先装入本行的物品，然后剩下背包容量装其他价值之和最大的物品

(2)不装本行物品，即背包容量都用来装除了本行物品之外的其他物品(即本行前面几行的物品)
然后比较(1)(2)选择较大者；

拿a【2】【4】来说，此时的背包容量为4,编号为2的物品的体积为3，故2号物品能装入背包，然后两种选择：
(1)装入2号物品，此时背包剩余容量为1，此时只剩下两个物品，那就是编号为0和1的物品，查表得a【1】【1】=0

故此时的最大价值为a【1】【1】加上2号物品的价值，也就是4

(2)不装2号物品，即背包容量都用来装除了本行物品之外的其他物品(即本行前面几行的物品)
由于不装入2号物品，此时的最大价值和只考虑编号为0，1物品，背包容量为4的情况的最大价值(即a【1】【4】)是相等的，
也就是3；

故选择(1)(2)中较大者，a【2】【4】=4;

依次类推下去。

解法归纳:

一、如果装不下当前物品，那么前n个物品的最佳组合和前n-1个物品的最佳组是一
样的。

二、如果装得下当前物品。

假设1:装当前物品，在给当前物品预留了相应空间的情况下，前n-1 个物品的最佳组
合加上当前物品的价值就是总价值。

假设2:不装当前物品，那么前n个物品的最佳组合和前n-1个物品的最佳组合是一样
的。

选取假设1和假设2中较大的价值，为当前最佳组合的价值。

代码实现

package eunm.Try;

//0-1背包问题
public class BB {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        int volume[] = {2, 3, 4, 5};
        int value[] = {3, 4, 5, 6};
        int maxvolume = 9;
        System.out.println(knapsack(volume, value, maxvolume));
    }

    public static int knapsack(int[] volume, int[] value, int maxvolume) {

        int n = volume.length;
        //最大价值数组为maxvalue[N+1][maxvolume+1]，因为我们要从0开始保存
        int[][] maxvalue = new int[n + 1][maxvolume + 1];

        //体积和物品为0时，价值为0
        for (int j = 0; j < maxvolume + 1; j++) {
            maxvalue[0][j] = 0;
        }
        for (int i = 0; i < n + 1; i++) {
            maxvalue[i][0] = 0;
        }

        //i：只拿前i件物品（这里的i因为取了0，所以对应到weight和value里面都是i-1号位置）
        //j：假设能取的总体积为j
        //n是物品件数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= maxvolume; j++) {
                //当前最大价值等于放上一件的最大价值
                maxvalue[i][j] = maxvalue[i - 1][j];
                //如果当前件的体积小于总体积，可以放进去或者拿出别的东西再放进去
                if (volume[i - 1] <= j) {
                    /*
                    比较（不放这个物品的价值）和
                    （这个物品的价值value[i - 1] 加上 当前能放的总体积减去当前物品体积j - volume[i - 1]
                     时取前i-1个物品时的对应体积时候的最高价值）maxvalue[i - 1][j - volume[i - 1]]的大小
                     */
                    if (value[i - 1] + maxvalue[i - 1][j - volume[i - 1]] > maxvalue[i - 1][j]) {
                        maxvalue[i][j] = value[i - 1] + maxvalue[i - 1][j - volume[i - 1]];
                    }
                }
            }
        }
        return maxvalue[n][maxvolume];
    }

}

这里比较关键。

//如果当前件的体积小于总体积，可以放进去或者拿出别的东西再放进去
                if (volume[i - 1] <= j) {
                    /*
                    比较（不放这个物品的价值）和
                    （这个物品的价值value[i - 1] 加上 当前能放的总体积减去当前物品体积j - volume[i - 1]
                     时取前i-1个物品时的对应体积时候的最高价值）maxvalue[i - 1][j - volume[i - 1]]的大小
                     */
                    if (value[i - 1] + maxvalue[i - 1][j - volume[i - 1]] > maxvalue[i - 1][j]) {
                        maxvalue[i][j] = value[i - 1] + maxvalue[i - 1][j - volume[i - 1]];
                    }
                }

背包问题回溯：在使得背包内总价值最大的情况下，背包内装了哪些物品?

这里我暂时不想研究了呜呜脑阔疼。

再来一个今天做的题目：小明是一个大胖子，为了让体重达到正常水平，他的计划是:减掉n千克体重,分多周完成(至少是2周)，每周都减重正整数千克。为了激励自己，他决定每周减掉的体重都必须比上周减掉的体重多。假设他上周减重0千克，他从这周开始执行计划，请问可以设计出多少种方案?

套一下上面的模板就行。

package Excepect;

import java.util.Scanner;

public class AAAA {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long[][] dp = new long[n][n + 1];
        dp[0][0] = 1;

        for (int i = 1; i < n; i++) {//i表示接收体重后体重变化
            dp[i][0] = 1;//第一周开始减最少从1开始
            for (int j = 1; j <= n; j++) {//j表示能减的总体重
                //当前方案=上一体重的方案
                dp[i][j] = dp[i - 1][j];
                //如果当前体重<=能减的总体重
                if (i <= j) {
                    //最多总方案=现有方案+（能减的总体重-当前体重时取前i-1对应体重的最多总方案）
                    dp[i][j] = dp[i][j] + dp[i - 1][j - i];
                }
            }
        }
        System.out.println(dp[n - 1][n]);
        scan.close();
    }
}