算法学习（三）——01背包

前言

挣扎了这么久以后，终于还是把01背包最简单的搞明白了。卡在01背包这里好几天了，看来我可能就不是一个打ACM的料，算了，还是好好学习算法把。

最基础的01背包模型

题目

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 个物品的体积和价值分别是 $w e i g h t [i]$ 和 $v a l u e [i]$ 。求解将哪些物品放进包里可以使价值最大。

特点

这类题目的很明显的特点是，每个物品都只有一个，可以选择要或者不要。

核心

01背包的题目很相似，其解题的核心也都是一样的，就是下面的状态转移方程：
tab[i][j]=max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j])
乍一看，这个所谓的状态转移方程属实有点难理解，我也是卡在这里很久很久才看明白，下面我就把我所理解的一一列出来。

状态转移方程讲解

$t a b [i] [j]$ 表示前 $i$ 件物品恰放入一个容量为 $j$ 的背包可以获得的最大价值
$i$ 表示放第 $i$ 个物品
$j$ 表示背包容量为 $j$
$w e i g h t [i]$ 表示第 $i$ 个物品的重量
$v a l u e [i]$ 表示第 $i$ 个物品的价值
$t a b [i - 1] [j - w e i g h t [i]] + v a l u e [i]$ 表示在装完前 $(i - 1)$ 个物品后再装入第 $(i)$ 个物品后的价值(如果可以装的下)
$t a b [i - 1] [j]$ 表示不装入第 $(i)$ 个物品的价值(因为装不下)
max()的第一个参数表示选择第 $i$ 个物品的情况，第二个参数表示不选择 $i$ 个物品的情况
注意 $i$ 要从1开始，因为总有一列tab[0][j]表示不装物品的空背包

以上就是我对于01背包的状态转移方程的理解，如果还是不理解的画，可以参考下面的例题：

例题

5个物品，（重量，价值）分别为：（5，12），（4，3），（7，10），（2，3），（6，6）。
然后我们可以通过状态转移方程得到下面的表格
Alt text
这里表格的横坐标为 $j$ ，纵坐标为 $i$
表格的具体分析可以参考上面状态转移方程的理解。

实现

for (int i=1;i<=m;i++){
	for (int j=0;j<=t;j++){
	          if (j<wight[i])//背包容量小于物品质量时
	              tab[i][j]=tab[i-1][j];
	          else
	              tab[i][j]=Math.max(tab[i-1][j-wight[i]]+values[i],tab[i-1][j]);
	}
}

复杂度分析

时间复杂度： $O (N V)$
空间复杂度： $O (N V)$

优化

这里的时间复杂度已经没有办法再优化了，可是空间复杂度却还有优化的余地。考虑我们的第二层循环，这里的每一个** $d p [i] [j]$ 的取值是都只和第二维比 $j$ **小的元素有关。那么是否可以通过改变枚举方向的方式，来把第一维用来保存当前位置的一列删掉呢。显然是可以的。考虑这样的代码：

for (int i = 0; i <= V; i++) dp[i] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = V; j >= C[i]; j--) {
        dp[j] = max(dp[j], dp[j-C[i]]+W[i]);
    }
}

实战

上面说了这么多，还没有真正实战一波，下面我找了一个学校的OJ上的题来小试牛刀一下。

采药【(0-1)背包问题】

Description

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？

Input

输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

Output

输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

Sample Input

70 3
71 100
69 1
1 2

Sample Output

3

AC代码

import java.util.Scanner;
/**
 * @program: oj
 * @description: https://www.oj.swust.edu.cn/problem/show/1046
 * @author: Pang
 * @create: 2018-10-25 15:36
 **/
public class Main{
    static Scanner scanner=new Scanner(System.in);
    static final int MAX_TIME=1005;//最大采药时间
    static final int MAX_CONT=105;//最大药品数量
    static int times[]=new int[MAX_TIME];//保存每颗药品需要的时间
    static int values[]=new int[MAX_CONT];//保存每颗药品的价值
    static int tab[][]=new int[MAX_CONT][MAX_TIME];//模拟背包
    public static void main(String args[]){
        int t=scanner.nextInt();//总共的采药时间
        int m=scanner.nextInt();//草药数目
        input(m);//输入草药的采集时间和价值
        for (int i=0;i<=m;i++){
            tab[0][i]=0;//表示采前0个药草的时候的最大价值为0
        }
        for (int i=1;i<=m;i++){
            for (int j=0;j<=t;j++){
                if (j<times[i])
                    tab[i][j]=tab[i-1][j];
                else
                    tab[i][j]=Math.max(tab[i-1][j-times[i]]+values[i],tab[i-1][j]);
            }
        }
        System.out.println(tab[m][t]);
    }
    /**
    * @Description: 输入药品的采集时间和价值
    * @Param:  草药数目
    * @return:  无
    * @Author: Pang
    * @Date: 2018/10/25
    */
    public static void input(int m){
        for (int i=1;i<=m;i++){
            times[i]=scanner.nextInt();
            values[i]=scanner.nextInt();
        }
    }
}

参考

基础动态规划

 最通俗易懂的01背包问题讲解

 01背包问题吐血详解

原文链接：https://blog.csdn.net/qq_40894516/article/details/83384282