演算法作業三_0-1 Double Knapsack Problem_4

user_3763047219
c_cpp
2 years ago
1.5 kB
4
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 pw = 0, pv = 0, T = 0, q = 0;
int ans[100] = { 0 };
static int t[101][1001][1001] = { 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]];
}
}
}
}
}

int text = 0;
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];
ans[text] = i;
text = text + 1;
}
}

for (int i = 0; i < text-1; i++) {
for (int j = 0; j < text - 1; j++) {
if (ans[j] > ans[j + 1]) {
int temp = 0;
temp = ans[j];
ans[j] = ans[j + 1];
ans[j + 1] = temp;
}
}
}

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