# 01Knapsack Problem 背包

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

int main()
{
int n = 0, W = 0, q = 0;
int v[101] = {}, w[101] = {};
static int T[101][101] = {};
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 = 1; i <= n; i++) {
int q2 = 0;
for (int j = 1; j <= W; j++) {
if (w[i] > j) {
T[i][j] = T[i - 1][j];
}
else {
if (T[i - 1][j] < T[i - 1][j - w[i]] + v[i]) {//維持原樣的 < 多放一個物品的價值
T[i][j] = T[i - 1][j - w[i]] + v[i];
}
else {
T[i][j] = T[i - 1][j];
}
}
}
}
int pw = W;
int T2 = 0;
int s[101] = {0};//紀錄是否要放第i個物品
int ans[101] = { 0 };
int index = 1;
for (int i = n; i >= 1; i--) {//從最後找回去
if (T[i][pw] == T[i - 1][pw]) {
s[i] = 0;
}
else {
s[i] = 1;
pw = pw - w[i];
T2 = T2 + v[i];
q = q + 1;
ans[index] = i;
index++;
}

}
printf("%d\n", T2);
printf("%d\n", q);
printf("(%d", ans[index-1]);

for (int i = index-2 ; i >= 1; i--) {
printf(",%d", ans[i]);
}
printf(")");
}```