# 105e Knapsack Problem

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

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

for (int i = 0; i <= n; i++) {
for (int j = 1; j <= W - w[1]; j++) {
c[i][j] = v[1];
}
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= W - w[1]; j++) {
if (w[i] > j) {
c[i][j] = c[i - 1][j];
}
else {
if (c[i - 1][j] < c[i - 1][j - w[i]] + v[i]) {
c[i][j] = c[i - 1][j - w[i]] + v[i];
}
else {
c[i][j] = c[i - 1][j];
}
}
}
}

int pw = W - w[1];
int ans[101] = {};
int value = v[1];
int total = 0;
for (int i = n; i >= 2; i--) {
if (c[i][pw] != c[i - 1][pw]) {
total = total + 1;
ans[total] = i ;
value = value + v[i];
pw = pw - w[i];
}
}
printf("%d\n%d\n", value , total+1);
printf("(1");
for (int i = total; i >= 1; i--) {
printf(",%d", ans[i]);
}
printf(")");

}