lintCode-92.背包问题.dp解法

忘是亡心i 2022-05-19 07:16 224阅读 0赞

*上周软考成绩出来了，当看到成绩的时候感觉还是有点小小的遗憾——差了5分。好几个周末都泡在图书馆里潜心修炼，尽管结果没能达到我的预期，但也让我发现了周末的新玩法-->**泡图书馆**，在通过以往几周的体验后发现其实这也是一种挺不错的选择方式，特别是炎热的夏天和寒冷的冬天，有免费的空调和安静的环境，哈哈。当然，对于上次的考试之所以挂了其中我的惰性和贪玩占了很大的因素，临近考试的那几个周末我还跑去各种玩的地方尽情嗨皮好几个整天，还有就是偶尔周末的早上起床比较晚，一上午的时间就这样耽误了，这是需要值得反思与克制的。还有就是我复习的方式也有问题，直接做题而没有看教程，这样导致基础知识点没有全面掌握过，考试结束后才发现对于软考其实是有复习教程的，而没弄一本过来就只知道看往年的试题对我貌似不适合，最终决定还是另辟蹊径，不能放弃。*

*有了前车之鉴后，立马从某宝上购了一本《软件设计师教程》打算11月的再战。这个周末的上海还是挺热的，周六下午泡了下午图书馆再次看到了算法部分，写得挺不错的。晚上回到家后打开电脑准备来找个简单的动态规划算法来练习一把。*

*————————————————————————————————————————————————————*

*————————————————————————分隔线—————————————————————————*

*————————————————————————————————————————————————————*

# 题目 #

来源：[https://www.lintcode.com][https_www.lintcode.com]

### 描述 ###

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\]

### **样例** ###

如果有4个物品**\[2, 3, 5, 7\]**

如果背包的大小为**11**，可以选择**\[2, 3, 5\]**装入背包，最多可以装满**10**的空间。

如果背包的大小为**12**，可以选择**\[2, 3, 7\]**装入背包，最多可以装满**12**的空间。

函数需要返回最多能装满的空间大小。

### **挑战** ###

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

我写的答案：

public class Main {
        public static void main(String[] args) {
            Main main = new Main();
            int i = main.backPack(10, new int[]{3, 4, 8, 5});
            System.out.println(">>>" + i);
        }
    
        /**
         * @param m: An integer m denotes the size of a backpack
         * @param A: Given n items with size A[i]
         * @return The maximum size
         * 如果有4个物品[2, 3, 5, 7]
         * 如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。
         * 如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。
         * 函数需要返回最多能装满的空间大小。
         * 10-->[3,4,8,5]
         */
        public int backPack(int m, int[] A) {
            if (m == 0 || A.length == 0) {
                return 0;
            }
            int length = A.length;
            int[][] array = new int[length + 1][m + 1];
            for (int i = 1; i <= length; i++) {
                for (int j = 1; j <= m; j++) {
                    if (A[i - 1] <= j) {
                        array[i][j] = Integer.max(array[i - 1][j - A[i - 1]] + A[i - 1], array[i - 1][j]);
                    } else {
                        array[i][j] = array[i - 1][j];
                    }
                }
            }
    
            showArray(array);
            return array[length][m];
        }
    
        private void showArray(int[][] array) {
            System.out.print("the 0-->");
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(j + "  ");
            }
            System.out.println();
            System.out.println();
            for (int i = 0; i < array.length; i++) {
                System.out.print("the " + i + "-->");
                for (int j = 0; j < array[0].length; j++) {
                    System.out.print(array[i][j] + "  ");
                }
                System.out.println();
            }
        }
    
    
    }

运行结果：

the 0-->0  1  2  3  4  5  6  7  8  9  10  
    
    the 0-->0  0  0  0  0  0  0  0  0  0  0  
    the 1-->0  0  0  3  3  3  3  3  3  3  3  
    the 2-->0  0  0  3  4  4  4  7  7  7  7  
    the 3-->0  0  0  3  4  4  4  7  8  8  8  
    the 4-->0  0  0  3  4  5  5  7  8  9  9  
    >>>9

**提交后通过。**

# 总结 #

对于需要用DP算法解决的题目在分析时如何定义所谓的动态转换方程是关键。

即这里的：**array\[i\]\[j\] = Integer.max(array\[i - 1\]\[j - A\[i - 1\]\] + A\[i - 1\], array\[i - 1\]\[j\]);**

具体步聚：

1、定义数组array\[i\]\[j\]为**在容量为j时在装入第i个物品时所能装下的物品重量最大值。**

2、画表格，找关系：**容量为j时装入第i个物品的重量最大值=max(在容量为j时装入第i个物品的重量+在容量为\[j-第i个物品的重量\]时所能装下的重量最大值，在容量为j时而没有装入第i个物品时所能装入物品重量的最大值)**

3、初始化array\[i\]\[j\]数组，即将没有装入任何物品时的最优值和容量为0时的最优值，上文由于是JAVA代码用int定义的，所以这个步聚可以省略

4、写代码，一行一行遍历，即装的物品从第1个到第N个这样一行一行遍历写表格

5、输出结果，即array数组的最后一个值

[https_www.lintcode.com]: https://www.lintcode.com