# 演算法作業0-1 Double Knapsack Problem

user_3763047219
c_cpp
2 years ago
1.2 kB
1
Indexable
Never
```#define _CRT_SCURE_NO_WARNINGS
#include <iostream>

int main() {
int N = 0, W = 0, V = 0;
int c[100] = { 0 }, w[100] = { 0 }, v[100] = { 0 };
int s[100] = { 0 };
int t[30][30][30] = {0},pw = 0, pv = 0, T = 0, q = 0;
scanf("%d", &N);
scanf("%d", &W);
pw = W;
scanf("%d", &V);
pv = 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]);
}

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] > c[i] + t[i - 1][j - w[i]][k - v[i]]) {
t[i][j][k] = t[i - 1][j][k];
}
else {
t[i][j][k] = c[i]+t[i - 1][j - w[i]][k - v[i]];
}
}
}
}
}

for (int i = N; i >= 1; i--) {
if (t[i][pw][pv] = t[i - 1][pw][pv]) {
s[i] = 0;
}
else {
s[i] = 1;
T = T + c[i];
q = q + 1;
pw = pw - w[i];
pv = pv - v[i];
}
}

printf("%d\n%d\n", T,q);
for (int i = 1; i <= N; i++) {
if (s[i] == 1) {
printf("%d", i);
}
}
}```