编辑代码

#include<stdio.h>
 
/**常量定义*/
#define N 5         //物品总数量
#define limit 10    //背包容量
#define true 1      //布尔类型
#define false 0     //布尔类型
 
/**类型定义*/
typedef enum{true_,false_} bool;//布尔类型
 
typedef struct
{
    int weight;//重量
    int value;//价值
} item;//物品
 
typedef struct
{
    bool solution[N];//解
    int value;//解的价值
    int weight;//解的重量
} resault;//结果
 
/**变量定义*/
item items[N] = {{6,5},{5,3},{4,5},{2,3},{1,6}};//物品集
 
/**回溯递归（物品集定义为全局变量）
*   传入参数：当前试探解，递归层数，最优解储存位置
    输出：当前最优试探解
*/
void findOptimum(resault test, int floor, resault* optimum)
{
    int i;//循环变量
    int restValue = 0;//剩余可获取价值
    if(floor >= N)//是否完成全部搜索
    {
        if(test.value > optimum->value) *optimum = test;//是否为更优解
    }
    else
    {
        if(test.weight + items[floor].weight <= limit)//若将本层物品放入且未超过容量
        {
            test.solution[floor] = true;//本结点层对应物品放入背包
            test.value += items[floor].value;
            test.weight += items[floor].weight;
            findOptimum(test, floor+1, optimum);//递归
            test.solution[floor] = false;//本结点层对应物品取出背包
            test.value -= items[floor].value;
            test.weight -= items[floor].weight;
        }
        for(i=floor+1; i<N; i++)//求除本结点层对应物品外剩余可获取价值
        {
            restValue += items[i].value;
        }
        if(optimum->value < test.value + restValue)//若当前总价值和剩余结点价值已超过或仍可能超过当前最优试探解
        {
            findOptimum(test, floor+1, optimum);//递归
        }
    }
}
 
/**结果展示函数*/
void showResault(resault* test)
{
    int i;
    printf("\n----------------------\n");
    printf("最优解：\n----------------------\n");
    printf("物品\t重量\t价值\n");
    for(i=0; i<N; i++)
    {
        if((test->solution)[i])
            printf("%d\t%dkg\t%d美元\n", i+1, items[i].weight, items[i].value);
    }
    printf("----------------------\n");
    printf("总量：\t%dkg\t%d美元\n", test->weight, test->value);
    printf("----------------------\n");
 
    printf("\n----------------------\n");
    printf("全部物品：\n----------------------\n");
    printf("物品\t重量\t价值\n");
    for(i=0; i<N; i++)
    {
        printf("%d\t%dkg\t%d美元\n", i+1, items[i].weight, items[i].value);
    }
    printf("----------------------\n");
    printf("背包容量：%dkg\n", limit);
    printf("----------------------\n");
}
 
/**主函数*/
int main()
{
    /*递归初始变量定义*/
    resault test = {{0},0, 0};//试探解 初始化为起点 同时作为最优解保存位置
    int floor = 0;//递归层数
 
    /*最优解查询函数调用*/
    findOptimum(test, floor, &test);
 
    /*展示最优解*/
    showResault(&test);
 
    return 0;
}