Approach

# 01背包問題

Time Complexity

n = size of vector capacity
m = sum of vector capacity
O(n * m)

Space Complexity

m = sum of vector capacity
O(m)

Code

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        int sum1 = 0, sum2 = 0, ans = 1e9;

        for (int i = 0 ; i < capacity.size() ; i++) {
            sum1 += capacity[i];
        }

        vector<int> dp(sum1 + 1, 1e9);

        dp[0] = 0;
        for (int i = 0 ; i < capacity.size() ; i++) {
            for (int j = sum1 ; j >= capacity[i] ; j--) {
                dp[j] = min(dp[j], dp[j - capacity[i]] + 1);
            }

            /*
            for (int i = 0 ; i <= sum1 ; i++) {
                cout << dp[i] << " ";
            }
            cout << endl;
            */
        }

        for (int i = 0 ; i < apple.size() ; i++) {
            sum2 += apple[i];
        }

        for (int i = sum2 + 1 ; i <= sum1 ; i++) {
            ans = min(ans, dp[i]);
        }

        return min(ans, dp[sum2]);
    }
};