编辑代码

#include <stdio.h>
#define NUM_ITEMS 5 // 物品个数
#define KNAPSACK_CAPACITY 10 // 背包容量
int weights[NUM_ITEMS] = {2, 3, 6, 5, 4}; // 物品重量
int values[NUM_ITEMS] = {66, 3953, 549, 40, 799}; // 物品价值
int maxValue = 0; // 最大价值
int solution[NUM_ITEMS] = {0}; // 最优解
int currentWeight = 0; // 当前重量
int currentValue = 0; // 当前价值

void backtrack(int i)
{
    if (i >= NUM_ITEMS) // 超出物品个数
    {
        if (currentValue > maxValue) // 更新最优解
        {
            maxValue = currentValue;
            for (int j = 0; j < NUM_ITEMS; j++)
                solution[j] = (j == 0) ? currentWeight : solution[j - 1];
        }
        return;
    }
    if (currentWeight + weights[i] <= KNAPSACK_CAPACITY) // 选择当前物品
    {
        currentWeight += weights[i];
        currentValue += values[i];
        backtrack(i + 1);
        currentWeight -= weights[i];
        currentValue -= values[i];
    }
    backtrack(i + 1); // 不选择当前物品
}

int main()
{
    backtrack(0);
    printf("物品重量为:");
    for (int i = 0; i < NUM_ITEMS; i++)
        printf("%d ", weights[i]);
    printf("\n");

    printf("物品价值为:");
    for (int i = 0; i < NUM_ITEMS; i++)
        printf("%d ", values[i]);
    printf("\n");

    printf("最大价值为: %d\n", maxValue);
    printf("最优解为:");
    for (int i = 0; i < NUM_ITEMS; i++)
        printf("%d ", solution[i]);
    printf("\n");

    return 0;
}