编辑代码

#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <limits.h>  // 添加这一行以引入LLONG_MAX宏定义

// 全局变量用于存储最优解
int bestValue = 0;
int bestChoice[100]; // 假设最大物品数量为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; // 最好情况下赋值次数

// 回溯法解决0-1背包问题
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; // 随机生成3-8个物品
            for (int i = 0; i < n; i++) {
                V[i] = rand() % 10 + 5; // 价值在5-14之间
                W[i] = rand() % 5 + 2;  // 重量在2-6之间
            }
            b = rand() % 10 + 10; // 背包容量在10-19之间
        }
        
        // 打印物品信息
        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++; // C > bestValue 
        if (C > bestValue) {
            assignments++; // i = i + 1
            i = i + 1;
            
            comparisons++; // i >= n
            if (i >= n) {
                // 到达叶节点,更新最优解
                comparisons++; // cv > bestValue
                if (cv > bestValue) {
                    assignments++; // bestValue = cv
                    bestValue = cv;
                    for (int j = 0; j < n; j++) {
                        assignments++; // bestChoice[j] = X[j]
                        bestChoice[j] = X[j];
                    }
                }
                assignments++; // i = Back(...)
                i = Back(i, n, X, V, W, cv, cw);
            } else {
                comparisons++; // cw + W[i] <= b
                if (cw + W[i] <= b) {
                    // 选择第i个物品
                    assignments += 3; // cv = cv + V[i], cw = cw + W[i], X[i] = 1
                    cv = cv + V[i];
                    cw = cw + W[i];
                    X[i] = 1;
                } else {
                    // 不选择第i个物品
                    assignments++; // X[i] = 0
                    X[i] = 0;
                }
            }
        } else {
            assignments++; // i = Back(...)
            i = Back(i, n, X, V, W, cv, cw);
        }
        
        comparisons++; // i < 0
        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) {
        // 修改后的逻辑:先检查i是否为0,再检查X[i]
        comparisons++; // i == 0
        if (i == 0) {
            comparisons++; // X[i] == 1
            if (X[i] == 1) {
                assignments++; // return -1
                return -1; // 回溯结束
            }
        }
        
        comparisons++; // X[i] == 1
        if (X[i] == 1) {
            assignments += 2; // cv = cv - V[i], cw = cw - W[i]
            cv = cv - V[i];
            cw = cw - W[i];
            
            comparisons++; // i < n - 1
            if (i < n - 1) {
                assignments += 2; // X[i] = 0, return i
                X[i] = 0;
                return i;
            } else {
                assignments++; // i = i - 1
                i = i - 1;
            }
        } else {
            assignments++; // i = i - 1
            i = i - 1;
        }
        
        comparisons++; // i < 0
        if (i < 0) {
            assignments++; // return -1
            return -1;
        }
    }
}

int Cost(int i, int n, int cv, int V[])
{
    int c = cv;
    assignments++; // c = cv
    
    for (int j = i + 1; j < n; j++) {
        comparisons++; // j < n
        assignments++; // c = c + V[j]
        c = c + V[j];
    }
    
    return c;
}