You are viewing a single comment's thread. Return to all comments →
using namespace std;
int knapsack(int W, vector& values, vector& weights) { int n = values.size(); vector> dp(n + 1, vector(W + 1, 0));
for (int i = 1; i <= n; ++i) { for (int w = 1; w <= W; ++w) { if (weights[i - 1] <= w) { dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); } else { dp[i][w] = dp[i - 1][w]; } } } return dp[n][W];
}
int main() { int n; cin >> n;
vector<int> values(n); vector<int> weights(n); for (int i = 0; i < n; ++i) { cin >> values[i] >> weights[i]; } int W; cin >> W; int result = knapsack(W, values, weights); cout << result << endl; return 0;
Seems like cookies are disabled on this browser, please enable them to open this website
Knapsack
You are viewing a single comment's thread. Return to all comments →
include
include
include
using namespace std;
int knapsack(int W, vector& values, vector& weights) { int n = values.size(); vector> dp(n + 1, vector(W + 1, 0));
}
int main() { int n; cin >> n;
}