[LintCode] Backpack I & II

atinosun 发布于2019-08-14 15:25 / 1297人阅读

摘要：动规经典题目，用数组表示书包空间为的时候能装的物品最大容量。注意的空间要给，因为我们要求的是第个值，否则会抛出。依然是以背包空间为限制条件，所不同的是取的是价值较大值，而非体积较大值。

Backpack Problem

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Notice

You can not divide any item into small pieces.

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Challenge

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.

Note

动规经典题目，用数组dp[i]表示书包空间为i的时候能装的A物品最大容量。两次循环，外部遍历数组A，内部反向遍历数组dp，若j即背包容量大于等于物品体积A[i]，则取前i-1次循环求得的最大容量dp[j]，和背包体积为j-A[i]时的最大容量dp[j-A[i]]与第i个物品体积A[i]之和即dp[j-A[i]]+A[i]的较大值，作为本次循环后的最大容量dp[i]。

注意dp[]的空间要给m+1，因为我们要求的是第m+1个值dp[m]，否则会抛出OutOfBoundException。

Solution

public class Solution {
    public int backPack(int m, int[] A) {
        int[] dp = new int[m+1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j > 0; j--) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j], dp[j-A[i]] + A[i]);
                }
            }
        }
        return dp[m];
    }
}

Backpack II Problem

Given n items with size A[i] and value V[i], and a backpack with size m. What"s the maximum value can you put into the backpack?

Notice

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

Challenge

O(n x m) memory is acceptable, can you do it in O(m) memory?

Note

和BackPack I基本一致。依然是以背包空间为限制条件，所不同的是dp[j]取的是价值较大值，而非体积较大值。所以只要把dp[j-A[i]]+A[i]换成dp[j-A[i]]+V[i]就可以了。

Solution

public class Solution {
    public int backPackII(int m, int[] A, int V[]) {
        int[] dp = new int[m+1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j > 0; j--) {
                if (j >= A[i]) dp[j] = Math.max(dp[j], dp[j-A[i]]+V[i]);
            }
        }
        return dp[m];
    }
}

GPU服务器私有云 II ii6 ii7 Backpack

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65754.html

[LintCode] Backpack I II III IV V VI [背包六问]

摘要：单次选择最大体积动规经典题目，用数组表示书包空间为的时候能装的物品最大容量。注意的空间要给，因为我们要求的是第个值，否则会抛出。依然是以背包空间为限制条件，所不同的是取的是价值较大值，而非体积较大值。 Backpack I Problem 单次选择+最大体积 Given n items with size Ai, an integer m denotes the size of a b...

sutaking 2019-08-14 14:31 评论0 收藏0
[LintCode/LeetCode] Subsets &amp; Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 评论0 收藏0
[LintCode/LeetCode] Single Number I &amp; II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0
[LintCode] Spiral Matrix I &amp; Spiral Matrix II

摘要：如果不在前两个循环之后的话，那么那多余的一行或一列就会被加入数组两次，造成错误的结果。解法和一样，只是简化了，甚至可以用一样的方法去做，只要把也换成。使用，以及最后讨论是否为奇数以判断中间是否有一个未循环的点，是这道题的两个有趣的地方。 Spiral Matrix I Problem Given a matrix of m x n elements (m rows, n columns...

tuantuan 2019-08-14 15:19 评论0 收藏0
[LintCode/LeetCode] Combination Sum I &amp; II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0