# 演算法作業三_0-1 Double Knapsack Problem

user_3763047219
c_cpp
2 years ago
1.3 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_all[100] = { 0 }, pw = 0,pv=0,T=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]);
}
t_all[0] = 0;
int i = 1;
int t_index = 1;
while (pw>0 && pv>0) {
int q = -1;
for (int j = i; j <= N; j++) {
for (int k = j; k <= N; k++) {
if (w[i] > pw || v[i] > pv) {
}
else {
if (q > c[i] + (pw - w[j]) + (pv - v[k]) + t_all[t_index - 1]) {
q = q;
}
else {
q = c[i] + (pw - w[j]) + (pv - v[k]) + t_all[t_index - 1];
if (s[t_index - 1] > i) {
s[t_index] = s[t_index - 1];
s[t_index - 1] = i;
}
else {
s[t_index] = i;
}
}
}
}
}
pw = pw - w[i];
pv = pv - v[i];
T = T + c[i];
t_all[t_index] = q;
i = i + 1;
t_index = t_index + 1;
}

printf("%d\n%d\n", T,t_index);
printf("(%d",s[1]);
for (int i = 2; i <= t_index; i++) {
printf(",%d", s[i]);
}
printf(")");

}```