Simple and Clean Solution with O(n) space complexity


#1

int Solution::solve(const vector &A, const vector &B, const vector &C) {
int max_capacity = *max_element(A.begin(),A.end());
vector dp(max_capacity+1,INT_MAX);
dp[0] = 0;
for(int i = 1; i <=max_capacity; i++){
for(int j= 0; j < B.size(); j++){
int cur_capacity = B[j];
int cur_cost = C[j];
if(i-cur_capacity >=0 && dp[i] > (dp[i-cur_capacity] + cur_cost ) )
dp[i] = dp[i-cur_capacity] + cur_cost;
}
}
int min_cost = 0;
for(int i = 0; i < A.size(); i++){
min_cost+=dp[A[i]];
}
return min_cost;
}