41 lines
1.4 KiB
C
41 lines
1.4 KiB
C
#include <stdio.h>
|
|
#define ITEM_COUNT 5
|
|
#define CAPACITY 6
|
|
int weights[ITEM_COUNT + 1] = {0, 2, 3, 6, 5, 4}; // 物品重量，从1开始以匹配索引
|
|
int values[ITEM_COUNT + 1] = {0, 60, 30, 50, 40, 60}; // 物品价值，从1开始以匹配索引
|
|
int DP[ITEM_COUNT + 1][CAPACITY + 1] = {0}; // 动态规划数组
|
|
void bag01Ditui() {
|
|
for (int i = 1; i <= ITEM_COUNT; i++) {
|
|
for (int j = 0; j <= CAPACITY; j++) {
|
|
if (j >= weights[i]) {
|
|
DP[i][j] = (DP[i - 1][j] > DP[i - 1][j - weights[i]] + values[i])
|
|
? DP[i - 1][j]
|
|
: DP[i - 1][j - weights[i]] + values[i];
|
|
} else {
|
|
DP[i][j] = DP[i - 1][j];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
void printResult(int n, int v) {
|
|
int isAdd[ITEM_COUNT + 1] = {0}; // 记录物品放置情况
|
|
for (int i = n; i >= 1; i--) {
|
|
if (DP[i][v] == DP[i - 1][v])
|
|
isAdd[i] = 0; // 不放此物品
|
|
else {
|
|
isAdd[i] = 1; // 放此物品
|
|
v -= weights[i]; // 减去相应的重量
|
|
}
|
|
}
|
|
for (int i = 1; i <= n; i++) {
|
|
printf(" %d号%s; ", i, isAdd[i] ? "放" : "不放");
|
|
}
|
|
printf("\n");
|
|
}
|
|
int main() {
|
|
bag01Ditui(); // 计算动态规划数组
|
|
printf("最大价值为: %d\n", DP[ITEM_COUNT][CAPACITY]);
|
|
printResult(ITEM_COUNT, CAPACITY); // 打印物品放置情况
|
|
return 0;
|
|
}
|