52 lines
1.8 KiB
C
52 lines
1.8 KiB
C
|
#include <stdio.h>
|
||
|
|
#include <stdlib.h>
|
||
|
|
typedef struct Goods{
|
||
|
|
int weight;
|
||
|
|
int value;
|
||
|
|
} Goods;
|
||
|
|
int getSurplusValue(Goods *goodArr, int n, int i) {
|
||
|
|
int surplusValue = 0;
|
||
|
|
for (int j = i; j < n; j++)
|
||
|
|
surplusValue += goodArr[j].value;
|
||
|
|
return surplusValue;
|
||
|
|
}
|
||
|
|
int dfs(Goods *goodArr, int n, int totalWeight, int *way, int *bestWay,
|
||
|
|
int i, int currWeight, int currValue, int bestValue) {
|
||
|
|
if (i >= n) {
|
||
|
|
bestValue = currValue;
|
||
|
|
for (int k = 0; k < n; k++)
|
||
|
|
bestWay[k] = way[k];
|
||
|
|
return bestValue;
|
||
|
|
}
|
||
|
|
// 搜索左子树
|
||
|
|
if (currWeight + goodArr[i].weight <= totalWeight) {
|
||
|
|
currWeight += goodArr[i].weight;
|
||
|
|
currValue += goodArr[i].value;
|
||
|
|
way[i] = 1;
|
||
|
|
bestValue = dfs(goodArr, n, totalWeight, way, bestWay, i + 1,
|
||
|
|
currWeight, currValue, bestValue);
|
||
|
|
currWeight -= goodArr[i].weight;
|
||
|
|
currValue -= goodArr[i].value;
|
||
|
|
way[i] = 0;
|
||
|
|
}
|
||
|
|
// 搜索右子树
|
||
|
|
if (currValue + getSurplusValue(goodArr, n, i + 1) >= bestValue) {
|
||
|
|
bestValue = dfs(goodArr, n, totalWeight, way, bestWay, i + 1,
|
||
|
|
currWeight, currValue, bestValue);
|
||
|
|
}
|
||
|
|
return bestValue;
|
||
|
|
}
|
||
|
|
int main() {
|
||
|
|
Goods goodArr[] = { {1, 5}, {2, 6}, {3, 7}, {4, 8} };
|
||
|
|
int totalWeight = 8;
|
||
|
|
int n = sizeof(goodArr) / sizeof(goodArr[0]);
|
||
|
|
int way[n], bestWay[n];
|
||
|
|
int bestValue = 0;
|
||
|
|
bestValue = dfs(goodArr, n, totalWeight, way, bestWay, 0, 0, 0, bestValue);
|
||
|
|
printf("最大价值可为: %d\n", bestValue);
|
||
|
|
printf("各包的取舍状态为：\n");
|
||
|
|
for (int i = 0; i < n; i++)
|
||
|
|
printf("重量为: %d 的: %d\n", goodArr[i].weight, bestWay[i]);
|
||
|
|
return 0;
|
||
|
|
}
|