Backpack

Description

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.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    // --------------------------------------------------------------
    // Version 1, O(n^2) s(n^2)
    int backPack(int m, vector<int> nums) {
        // write your code here
        if (nums.empty() || m <= 0) {
            return 0;
        }
        int len = nums.size();
        vector<vector<bool>> dp(len + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < m + 1; ++j) {
                dp[i+1][j] = dp[i][j];
                // make sure: cur j > nums[i] 
                // and [j-nums[i]] can be selected, so we can validate [j]
                if (j >= nums[i] && dp[i][j-nums[i]]) {
                    dp[i+1][j] = true;
                }
            }
        }
        for (int i = m; i >= 0; --i) {
            if (dp[len][i]) {
                return i;
            }
        }
        return 0;
    }
    // ----------------------------------------------------------------
    // Version 2, O(n^2) s(n)
    // reuse the dp[] array
    int backPack(int m, vector<int> nums) {
        // write your code here
        if (nums.empty() || m <= 0) {
            return 0;
        }
        int len = nums.size();
        // reused array
        vector<bool> dp(m + 1, false);
        dp[0] = true;
        for (int i = 0; i < len; ++i) {
            for (int j = m; j >= nums[i]; --j) {
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        for (int i = m; i >= 0; --i) {
            if (dp[i]) {
                return i;
            }
        }
        return 0;
    }
    // ----------------------------------------------------------------
};

Similar problems

x

Tags

x