I’m trying to solve the Knapsack 01 problem but my code gives me the WA for some test cases.
Problem link: D - Knapsack 1
Code:
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
int n, wt; // n = No. of items #### wt = Total capacity
cin >> n >> wt;
pair<ll, ll> items[n];
for (int i = 0; i < n; i++) {
cin >> items[i].first; // Weight
cin >> items[i].second; // Value
}
ll val[n + 1][wt + 1];
for (int i = 0; i <= n; i++) { // Item number
for (int w = 0; w <= wt; w++) { // Weight number
if (i == 0 || w == 0) val[i][w] = 0; // If item number is 0 or weight is 0 then value is also 0.
else if (items[i - 1].first <= wt) {
ll CurWt = items[i - 1].first;
ll CurVal = items[i - 1].second;
val[i][w] = max(val[i - 1][w], val[i - 1][w - CurWt] + CurVal);
} else val[i][w] = val[i - 1][w];
}
}
cout << val[n][wt];
}