编辑代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Item {
    char name[20];
    int weight;
    int value;
    struct Item *next;
};

struct Result {
    int value;
    struct Item *head;
};

struct Item* createItem(const char* n, int w, int v) {
    struct Item* item = (struct Item*)malloc(sizeof(struct Item));
    strcpy(item->name, n);
    item->weight = w;
    item->value = v;
    item->next = NULL;
    return item;
}

struct Result* createResult() {
    struct Result* result = (struct Result*)malloc(sizeof(struct Result));
    result->value = 0;
    result->head = createItem("", 0, 0);
    return result;
}

struct Item* copyItem(struct Item* item) {
    struct Item* newItem = (struct Item*)malloc(sizeof(struct Item));
    strcpy(newItem->name, item->name);
    newItem->weight = item->weight;
    newItem->value = item->value;
    newItem->next = item->next;
    return newItem;
}

struct Result* copyResult(struct Result* result) {
    struct Result* newResult = (struct Result*)malloc(sizeof(struct Result));
    newResult->value = result->value;
    newResult->head = createItem("", 0, 0);
    newResult->head->next = result->head->next;
    return newResult;
}

struct Result* backpack(int packCapacity, struct Item* items, int itemCount) {
    
    int minWeight = items[0].weight;

    for (int i = 1; i < itemCount; ++i) {
        int curWeight = items[i].weight;
        if (curWeight < minWeight) {
            minWeight = curWeight;
        }
    }

    if (packCapacity < minWeight) {
        printf("The capacity of package %d is less than the minimum weight of items %d\n", packCapacity, minWeight);
        return NULL;
    }

    struct Result** dpArray = (struct Result**)malloc(itemCount * sizeof(struct Result*));
    int weightCount = packCapacity + 1;

    for (int i = 0; i < itemCount; ++i) {
        dpArray[i] = (struct Result*)malloc(weightCount * sizeof(struct Result));
    }

    for (int i = 0; i < itemCount; ++i) {
    // 记录放入背包物品的重量和价值
    int curWeight = items[i].weight;
    int curValue = items[i].value;
    for (int w = minWeight; w < weightCount; ++w) {
        // 记录不放入当前物品的情况下,放入背包物品能够达到的最大价值
        int preTotalValue = 0;

        if (i > 0) {
            preTotalValue = dpArray[i - 1][w].value;
        }

        // 记录放入当前物品的情况下,放入背包物品能够达到的最大价值
        int curTotalValue = 0;

        // 如果当前物品能够放入背包,记录下物品的价值
        if (w >= curWeight) {
            curTotalValue = curValue;
        }
        // 如果放入当前物品后背包还能放入其它物品,且确实还有其它物品,加上剩余的小背包能够放入物品的最大价值
        if (w > curWeight && i > 0) {
            curTotalValue += dpArray[i - 1][w - curWeight].value;
            struct Item *newItem = (struct Item *)malloc(sizeof(struct Item));
            strcpy(newItem->name, items[i].name);
            newItem->weight = items[i].weight;
            newItem->value = items[i].value;
            newItem->next = dpArray[i - 1][w - curWeight].head->next;
            dpArray[i][w].head->next = newItem;
        }

        // 找出放入当前物品和不放入当前物品情况下,放入背包的物品能够达到的最大价值
        int maxTotalValue = preTotalValue;

        if (maxTotalValue < curTotalValue) {
            maxTotalValue = curTotalValue;
            struct Item *newItem = (struct Item *)malloc(sizeof(struct Item));
            strcpy(newItem->name, items[i].name);
            newItem->weight = items[i].weight;
            newItem->value = items[i].value;
            newItem->next = dpArray[i][w].head->next;
            items[i].next = dpArray[i][w].head->next;
            dpArray[i][w].head->next = newItem;
        } else {
            dpArray[i][w].head->next = dpArray[i - 1][w].head->next;
        }

        // 记录下放入当前物品后,能够放w磅物品的背包能够放入物品的最大价值
        dpArray[i][w].value = maxTotalValue;
    }
}

    struct Result *result = (struct Result *)malloc(sizeof(struct Result));
    result->value = dpArray[itemCount - 1][weightCount - 1].value;
    result->head = copyItem(dpArray[itemCount - 1][weightCount - 1].head);

    // Cleanup
    for (int i = 0; i < itemCount; ++i) {
        for (int j = 0; j < weightCount; ++j) {
            free(dpArray[i][j].head);
        }
        free(dpArray[i]);
    }
    free(dpArray);

    return result;
}

int main() {
    int packCapacity = 4;
    struct Item items[]= {
        {"Guitar", 1, 1500, NULL},
        {"Sound Equipment", 4, 3000, NULL},
        {"Notebook", 3, 2000, NULL}, 
        {"IPhone", 1, 2000, NULL}}; 
    int itemCount = sizeof(items)/sizeof(struct Item);
    struct Result* result = NULL;
    result = backpack(packCapacity, items, itemCount);

    if (result->value > 0) {
        printf("最大值为%d\n", result->value);
        struct Item *item = result->head->next;
        struct Item *prev = NULL;
        printf("Objects are ");
        while (item != NULL) {
            printf("%s, ", item->name);
            prev = item;
            item = item->next;
            free(prev);
        }
        printf("\n");
    }
    free(result->head);
    free(result);
    return 0;
}