Double Knapsack Problem

user_3763047219
c_cpp
2 years ago
1.1 kB
1
Indexable
Never
```#include <iostream>

int main()
{
int n = 0, W = 0, V = 0;
int c[101] = {}, w[101] = {}, v[101] = {};
scanf("%d%d%d", &n, &W, &V);
for (int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
}

static int T[101][1001][1001] = {0};
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
for (int k = 1; k <= V; k++) {
if (w[i] > j || v[i] > k) {
T[i][j][k] = T[i - 1][j][k];
}
else {
if (T[i - 1][j][k] < T[i - 1][j - w[i]][k - v[i]] + c[i]) {
T[i][j][k] = T[i - 1][j - w[i]][k - v[i]] + c[i];
}
else {
T[i][j][k] = T[i - 1][j][k];
}
}
}
}
}

int pw = W, pv = V;
int value = 0;
int total = 0;
int ans[101] = {};
for (int i = n; i >= 1; i--) {
if (T[i][pw][pv] != T[i - 1][pw][pv]) {
value = value + c[i];
total++;
ans[total] = i;
pw = pw - w[i];
pv = pv - v[i];
}
}

printf("%d\n%d\n", value, total);
for (int i = total; i >= 1; i--) {
printf("%d ", ans[i]);
}
}```