0-1 Knapsack

• Time : $O(ca)$
• Space : $O(c)$

int Solution::solve(vector<int> &A, vector<int> &B, int C) {
    vector<int> dp(C + 1, INT_MIN);
    dp[0] = 0;
    for(int i = 0; i < A.size(); i++) {
        int a = A[i], b = B[i];
        for(int j = C; j >= b; j--) {
            dp[j] = max(dp[j], dp[j-b] + a);
        }
    }
    
    return *max_element(begin(dp),end(dp));
}