#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <limits.h> // 添加这一行以引入LLONG_MAX宏定义
int bestValue = 0;
int bestChoice[100];
long long comparisons = 0;
long long assignments = 0;
long long worstComparisons = 0;
long long worstAssignments = 0;
long long avgComparisons = 0;
long long avgAssignments = 0;
long long bestComparisons = LLONG_MAX;
long long bestAssignments = LLONG_MAX;
int BackTrackingKnapsack(int n, int b, int W[], int V[]);
int Back(int i, int n, int X[], int V[], int W[], int cv, int cw);
int Cost(int i, int n, int cv, int V[]);
int main()
{
int experiments = 10;
int n = 4;
int b;
int V1[4] = {12, 11, 9, 8};
int W1[4] = {8, 6, 4, 3};
int V[100], W[100];
srand(time(NULL));
for (int exp = 1; exp <= experiments; exp++) {
printf("\n===== 实验 %d =====\n", exp);
comparisons = 0;
assignments = 0;
if (exp == 1) {
memcpy(V, V1, 4 * sizeof(int));
memcpy(W, W1, 4 * sizeof(int));
b = 13;
} else {
n = rand() % 6 + 3;
for (int i = 0; i < n; i++) {
V[i] = rand() % 10 + 5;
W[i] = rand() % 5 + 2;
}
b = rand() % 10 + 10;
}
printf("物品数量: %d\n", n);
printf("物品价值: [");
for (int i = 0; i < n; i++) {
printf("%d", V[i]);
if (i < n - 1) printf(",");
}
printf("]\n");
printf("物品重量: [");
for (int i = 0; i < n; i++) {
printf("%d", W[i]);
if (i < n - 1) printf(",");
}
printf("]\n");
printf("背包容量: %d\n", b);
int result = BackTrackingKnapsack(n, b, W, V);
if (comparisons > worstComparisons) {
worstComparisons = comparisons;
worstAssignments = assignments;
}
if (comparisons < bestComparisons) {
bestComparisons = comparisons;
bestAssignments = assignments;
}
avgComparisons += comparisons;
avgAssignments += assignments;
printf("最大价值: %d\n", result);
printf("选择的物品: [");
for (int i = 0; i < n; i++) {
if (bestChoice[i] == 1) {
printf("%d", i+1);
if (i < n - 1 && bestChoice[i+1] == 1) printf(",");
}
}
printf("]\n");
printf("比较次数: %lld\n", comparisons);
printf("赋值次数: %lld\n", assignments);
printf("总次数:%lld\n",(comparisons+assignments));
}
printf("\n===== 总体性能统计 =====\n");
printf("最坏情况: 比较次数=%lld, 赋值次数=%lld\n", worstComparisons, worstAssignments);
printf("平均情况: 比较次数=%lld, 赋值次数=%lld\n", avgComparisons/experiments, avgAssignments/experiments);
printf("最好情况: 比较次数=%lld, 赋值次数=%lld\n", bestComparisons, bestAssignments);
return 0;
}
int BackTrackingKnapsack(int n, int b, int W[], int V[])
{
int i = 0;
int cv = 0;
int cw = 0;
int X[100] = {0};
bestValue = 0;
comparisons++;
while (1) {
int C = Cost(i, n, cv, V);
assignments++;
comparisons++;
if (C > bestValue) {
assignments++;
i = i + 1;
comparisons++;
if (i >= n) {
comparisons++;
if (cv > bestValue) {
assignments++;
bestValue = cv;
for (int j = 0; j < n; j++) {
assignments++;
bestChoice[j] = X[j];
}
}
assignments++;
i = Back(i, n, X, V, W, cv, cw);
} else {
comparisons++;
if (cw + W[i] <= b) {
assignments += 3;
cv = cv + V[i];
cw = cw + W[i];
X[i] = 1;
} else {
assignments++;
X[i] = 0;
}
}
} else {
assignments++;
i = Back(i, n, X, V, W, cv, cw);
}
comparisons++;
if (i < 0) {
break;
}
}
return bestValue;
}
int Back(int i, int n, int X[], int V[], int W[], int cv, int cw)
{ comparisons++;
while (1) {
comparisons++;
if (i == 0) {
comparisons++;
if (X[i] == 1) {
assignments++;
return -1;
}
}
comparisons++;
if (X[i] == 1) {
assignments += 2;
cv = cv - V[i];
cw = cw - W[i];
comparisons++;
if (i < n - 1) {
assignments += 2;
X[i] = 0;
return i;
} else {
assignments++;
i = i - 1;
}
} else {
assignments++;
i = i - 1;
}
comparisons++;
if (i < 0) {
assignments++;
return -1;
}
}
}
int Cost(int i, int n, int cv, int V[])
{
int c = cv;
assignments++;
for (int j = i + 1; j < n; j++) {
comparisons++;
assignments++;
c = c + V[j];
}
return c;
}