动态规划-01背包滚动数组优化

------使用 java 编写，逻辑上所有语言通用

一、01 背包问题的优化

（1）例题

        现有一个 1 kg 价值为 15 元的苹果、一个 3 kg 价值为 20 元的哈密瓜 、一个 4kg 价值为 30 元的榴莲，用一个承重能力为 4 kg 的背包，问该背包能装入价值最大为多少元的水果？

（2）什么是滚动数组

         滚动数组是DP中的一种编程思想，简单理解就是让数组一边使用一边更新，每次使用固定的几个存储空间来达到压缩，节省存储空间；

（3）联合滚动数组进行解题

3.1

        根据我们之前得出的结论，我们只要得到 bag[i-1][ ? ] 就可以凭此求出 bag[i][ ? ] 的信息，而 bag[i-2][ ? ] 以及其之前的数据都是完全用不到的；

        那么我们是否可以通过把二维数组转换为一维数组进行存储呢？

        这时我们又会发现一个新的问题，因为 01 背包物品是不可以重复的，而使用之前的判断方式可能会出现计算后面重量的背包空间时早已将需要参加计算的数据进行更新了；

        难道转换成一维数组的方法不可取吗？

        当然不是，我们可以通过从数组尾部开始计算，使得更新的值不会影响到后续的计算；

3.2

        同样的，建立三个数组，一个存储重量，一个存储价值，一个存储每种情况下背包中水果的最大价值；（ 区别就是从二维数组转换成了一维数组 ）

 3.3

        循环也是相差无几，主要区别如下：

        1. 第二个循环更改为从末尾开始，到小于等于 0 结束；

        2. 当水果重量大于当前重量时更改为不做任何事情，直接通过 continue 跳过或者写一个 " ; " 代表空语句，因为前一种情况已经存储在了当前位置不用再次赋值；

        3. 水果重量小于等于当前重量时，也是通过同样的公式，注意二维数组改为一维数组即可；

 3.4

        最后直接输出数组中最后一个结果即为答案；

 

二、什么时候使用滚动数组

        滚动数组虽然降低了空间，但是也有弊端；

        因为使用滚动数组时一旦想要获取所装入的水果是什么时将无法做到；

        而使用二维数组存储可以通过一步步回溯寻找到使用到的水果，故如果需要将使用水果也打印出来时，滚动数组将不再适用；

三、代码分享

public class DP_New_01Bag {
    public static void main(String[] args) {
        int[] wight = { 0 , 1 , 3 , 4 };
        int[] money = { 0 , 15 , 20 , 35 };
        int[] dp = new int[5];
        for (int i = 1; i < wight.length; i++) {
            for (int j = dp.length - 1; j > 0; j--) {
                if ( wight[i] > j )
                    continue;
                else dp[j] = Math.max( dp[j] , money[i] + dp[j - wight[i]] );
            }
        }
        System.out.println( dp[dp.length - 1] );
    }
}