[LintCode] Backpack I & II

atinosun 發布于2019-08-14 15:25 / 1387人閱讀

摘要：動規經典題目，用數組表示書包空間為的時候能裝的物品最大容量。注意的空間要給，因為我們要求的是第個值，否則會拋出。依然是以背包空間為限制條件，所不同的是取的是價值較大值，而非體積較大值。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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