60 lines
2.1 KiB
C
60 lines
2.1 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
#define MAX_N 100 // 最大集装箱数量
|
|
int n; // 集装箱数
|
|
int boxArr[MAX_N]; // 集装箱重量数组
|
|
int C1; // 第一艘轮船的载重量
|
|
int currWeight = 0; // 当前载重量
|
|
int bestWeight = 0; // 当前最优载重量
|
|
int bestx[MAX_N]; // 最佳装入数组 当前最优解
|
|
int x[MAX_N]; // 装入数组 当前解
|
|
|
|
void backtrace(int i, int leftWeight) {//i集装箱索引，leftWeight剩余重量
|
|
// 1. 到达叶节点
|
|
if (i >= n) { // i此时的值=叶节点+1
|
|
if (currWeight > bestWeight) {
|
|
for (int j = 0; j < n; j++) // 记录当前最佳解
|
|
bestx[j] = x[j];
|
|
bestWeight = currWeight;
|
|
}
|
|
return;
|
|
}
|
|
// 剪枝1：如果当前背包重量加上剩余的重量都无法超过当前最优解，直接返回
|
|
if (currWeight + leftWeight <= bestWeight) { return; }
|
|
// 2. 搜索左子树：选择装入第i个集装箱
|
|
if (currWeight + boxArr[i] <= C1) { // x[i] = 1
|
|
x[i] = 1;
|
|
currWeight += boxArr[i];
|
|
backtrace(i + 1, leftWeight - boxArr[i]); // 递归时更新剩余重量
|
|
currWeight -= boxArr[i]; // 回溯时撤销选择
|
|
}
|
|
// 3. 搜索右子树：不装入第i个集装箱
|
|
// 剪枝2：如果当前背包容量加上剩余集装箱总重量仍然无法找到更好的解，返回
|
|
if (currWeight + leftWeight > bestWeight) {
|
|
x[i] = 0;
|
|
backtrace(i + 1, leftWeight - boxArr[i]); // 递归时更新剩余重量
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
// 初始化集装箱信息
|
|
int boxes[] = {4, 5, 6};
|
|
n = sizeof(boxes) / sizeof(boxes[0]); // 货物数量
|
|
C1 = 10; // 第一艘轮船的载重量
|
|
int totalWeight = 0;
|
|
for (int i = 0; i < n; i++) {// 设置集装箱重量，并计算总重量
|
|
boxArr[i] = boxes[i];
|
|
totalWeight += boxArr[i];
|
|
}
|
|
// 调用回溯算法
|
|
backtrace(0, totalWeight);
|
|
// 输出最优方案
|
|
printf("当前最优方案:\n");
|
|
for (int i = 0; i < n; i++) {
|
|
printf("%d: %d\n", boxArr[i], bestx[i]);
|
|
}
|
|
printf("最优解：%d\n", bestWeight);
|
|
return 0;
|
|
}
|