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

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

if (s[t_index - 1] > text) {
s[t_index] = s[t_index - 1];
s[t_index - 1] = text;
}
else {
s[t_index] = text;
}
pw = pw - w[text];
pv = pv - v[text];
T = T + c[text];
t_index = t_index + 1;
c[text] = -2; w[text] = 0; v[text] = 0;
}

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