A Variation of Unbounded knapsack! C++

#1

int Solution::solve(const vector &A, const vector &B, const vector &C) {
vector A1;
vector B1;
vector C1;
A1=A;
B1=B;
C1=C;
sort(A1.begin(), A1.end());
int n = B1.size();
int w = A1[A1.size()-1];
int t[n+1][w+1];
int sum=0;

for(int i=0; i<n+1; i++) {
    t[i][0] = 0;
}

for(int j=0; j<w+1; j++) {
    t[0][j] = INT_MAX/2;
}

for(int i=1; i<n+1; i++) {
    for(int j=1; j<w+1; j++) {
        if(B1[i-1]<=j) {
            t[i][j] = min(C1[i-1] + t[i][j-B1[i-1]], t[i-1][j]);
        }
        else {
            t[i][j] = t[i-1][j];
        }
    }
}

for(int i=0; i<A1.size(); i++) {
    sum = sum + t[n][A1[i]];
}
return sum;

}

#2

Why did u initialize the first row with INT_MAX/2 and not by INT_MAX?

#3

@sneh2706 it is initialized like that to avoid integer overflow when u add C[i-1] to that value. If its INT_MAX then it will overflow and give some negative number and hence wrong ans. Though its not necessary to do INT_MAX/2 you can make any fair assumption. Mine worked for INT_MAX/10 as well. Exact limit could have been found out if constraints for cost were given in the question.