# 演算法 0-1 Double Knapsack Problem

user_6817964
c_cpp
2 years ago
2.0 kB
1
Indexable
Never
```#define CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
int c[101], w[101], v[101];
static int result[101][1001][1001] = {0}; //建空表格
int N, W, V;
scanf_s("%d%d%d", &N, &W, &V);
for (int i = 1; i <= N; i++) {
scanf_s("%d", &c[i]);//商品的價值
}
for (int i = 1; i <= N; i++) {
scanf_s("%d", &w[i]);//商品的重量
}
for (int i = 1; i <= N; i++) {
scanf_s("%d", &v[i]);//商品的體積
}

//填入表格
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= W; i++) {
for (int j = 1; j <= V; j++) {
//放不下(重量過重 || 體積太大)
if (i < w[k] || j < v[k])
result[k][i][j] = result[k - 1][i][j];
//放得下，要不要放?
else
result[k][i][j] = result[k - 1][i][j] > (c[k] + result[k - 1][i - w[k]][j - v[k]]) ? result[k - 1][i][j] : (c[k] + result[k - 1][i - w[k]][j - v[k]]);
}
}
}

//追溯選中的商品
int bagw = W;
int bagv = V;
int total = 0;
int get[101];
//倒回去判斷
for (int i = N; i >= 1; i--) {
//如果在指定承重量下，該商品對應的收益和上一个商品對應的收益相同，表示沒選到該商品
if (result[i][bagw][bagv] == result[i - 1][bagw][bagv]) {
//沒事
}
//被選到了
else {
total++;
get[total] = i; //被選到的商品號碼
bagw = bagw - w[i];//刪除被選到商品的重量體積
bagv = bagv - v[i];
}
}

printf("%d\n", result[N][W][V]); // 最大總價值
printf("%d\n", total); // 選了幾個商品
printf("(");

if (total > 0) {
printf("%d", get[total]);
}
for (int i = total - 1; i >= 1; i--) {
printf(",%d", get[i]);
}
printf(")");

}
```