Simple Solution Using 0/1 Knapsack with Filling Capacity as Weights and Cost as Value and instead of maximizing here we are minimizing the value


#1

int Solution::solve(const vector &A, const vector &B, const vector &C) {
vector<pair<int,int>> V(B.size());
for(int i=0;i<B.size();i++) V[i] = make_pair(B[i],C[i]);
sort(V.begin(),V.end());
int maxCap = INT_MIN; for(int i=0;i<A.size();i++) maxCap = max(maxCap,A[i]);
vector<vector> dp(B.size()+1,vector(maxCap+1,INT_MAX/2));
for(int i=0;i<dp.size();i++)dp[i][0] = 0;

for(int i=1;i<dp.size();i++){
    for(int j=1;j<dp[0].size();j++){
        if(V[i-1].first > j) dp[i][j] = dp[i-1][j];
        else {
            int upper = j/V[i-1].first;
            int minCost = dp[i-1][j];
            for(int k=0;k<=upper;k++){
                minCost = min(minCost,(dp[i-1][j-k*V[i-1].first] + V[i-1].second*k));
            }
            dp[i][j] = min(minCost,dp[i-1][j]);
        }
    }
}
int res = 0;
for(int i=0;i<A.size();i++) res += dp.back()[A[i]];
return res;

}