From 4e8ac826929117f95baeb37e1518773d1169d900 Mon Sep 17 00:00:00 2001 From: Mathias Magnusson Date: Wed, 28 Feb 2024 18:00:30 +0100 Subject: Random uncommited stuff --- kattis-open/knapsack/knapsack.c | 59 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) create mode 100644 kattis-open/knapsack/knapsack.c (limited to 'kattis-open/knapsack/knapsack.c') diff --git a/kattis-open/knapsack/knapsack.c b/kattis-open/knapsack/knapsack.c new file mode 100644 index 0000000..407b133 --- /dev/null +++ b/kattis-open/knapsack/knapsack.c @@ -0,0 +1,59 @@ +#include +#include + +int max(int a, int b) { + int v[2] = { a, b }; + return v[b > a]; +} + +int min(int a, int b) { + int v[2] = { a, b }; + return v[b < a]; +} + +int ks[2001][2001], v[2000], w[2000]; +bool t[2001][2001]; +int main() { + int c, n; + while (scanf("%d %d", &c, &n) == 2) { + for (int i = 0; i < n; i++) { + scanf("%d %d", &v[i], &w[i]); + } + + for (int j = 0; j < w[0] && j <= c; j++) { + ks[0][j] = 0; + t[0][j] = false; + } + for (int j = w[0]; j <= c; j++) { + ks[0][j] = v[0]; + t[0][j] = true; + } + + for (int i = 1; i < n; i++) { + for (int j = 0; j < w[i] && j <= c; j++) { + ks[i][j] = ks[i - 1][j]; + t[0][j] = false; + } + for (int j = w[i]; j <= c; j++) { + int skip = ks[i - 1][j]; + int take = ks[i - 1][j - w[i]] + v[i]; + ks[i][j] = max(take, skip); + t[i][j] = take > skip; + } + } + + int taken[2000]; + int taken_count = 0; + int j = c; + for (int i = n - 1; i >= 0; i--) { + if (t[i][j]) { + taken[taken_count++] = i; + j -= w[i]; + } + } + printf("%d\n", taken_count); + for (int i = taken_count - 1; i >= 0; i--) { + printf("%d%c", taken[i], i == 0 ? '\n' : ' '); + } + } +} -- cgit v1.2.3