Backpack C++ Solution Summary


  • 0
    F

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

    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
         */
        int backPack(int m, vector<int> A) {
            // table[i][j] denotes whether using the first elements
            // could fulfill size j.
            vector<vector<bool>> dp(A.size() + 1, vector<bool>(m + 1, false));
            if(m == 0 || A.size() == 0) {
                return 0;
            }
            for(int i = 0; i < m + 1; i++)   dp[0][i] = false;
            
            for(int i = 0; i < A.size() + 1; i++)  dp[i][0] = true;
            
            for(int i = 1; i < A.size() + 1; i++) {
                for(int j = 1; j < m + 1; j++) {
                    if(j - A[i-1] < 0) {
                        dp[i][j] = dp[i - 1][j];
                    }
                    else {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
                    }
                }
            }
            
            for(int i = m; i >= 0; i--) {
                if (dp[A.size()][i]) {
                    return i;
                }
            }
            return 0;
        }
    };
    
    

    2 Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

    class Solution {
    public:
        /**
         * @param m: An integer m denotes the size of a backpack
         * @param A & V: Given n items with size A[i] and value V[i]
         * @return: The maximum value
         */
        int backPackII(int m, vector<int> A, vector<int> V) {
            // write your code here
            vector<vector<int>> dp(A.size() + 1, vector<int>(m + 1, false));
            if(m == 0 || A.size() == 0) {
                return 0;
            }
            
            for(int i = 0; i < m + 1; i++)   dp[0][i] = 0;
            for(int i = 0; i < A.size() + 1; i++)  dp[i][0] = 0;
            
            for(int i = 1; i < A.size() + 1; i++) {
                for(int j = 1; j < m + 1; j++) {
                    if(j - A[i-1] < 0) {
                        dp[i][j] = dp[i - 1][j];
                    }
                    else {
                        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
                    }
                }
            }
            
            return dp[A.size()][m];
        }
    };
    
    

    3 Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

    class Solution {
    public:
        /**
         * @param nums an integer array and all positive numbers, no duplicates
         * @param target an integer
         * @return an integer
         */
        int backPackVI(vector<int>& nums, int target) {
            vector<int> dp(target + 1);
            dp[0] = 1;
            for (int i = 1; i <= target; ++i) {
                for (const auto& num : nums) {
                    if (i >= num) {
                        dp[i] += dp[i - num];
                    }
                }
            }
            return dp.back();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.