编辑代码

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

// 定义物品
struct Item {
    char name[50];
    int value;
    int weight;
};

// 偷东西的方法
// 输入：packCapacity：包的容量
//      items： 可以偷的物品
// 输出：偷的物品集合
struct Item* stealObject(int packCapacity, struct Item* items, int itemCount) {
    // 创建动态规划表格
    int **dpTable = (int **)malloc((itemCount + 1) * sizeof(int *));
    for (int i = 0; i <= itemCount; i++) {
        dpTable[i] = (int *)malloc((packCapacity + 1) * sizeof(int));
        memset(dpTable[i], 0, (packCapacity + 1) * sizeof(int));
    }

    // 填充动态规划表格
    for (int i = 1; i <= itemCount; i++) {
        for (int j = 1; j <= packCapacity; j++) {
            if (items[i - 1].weight > j) {
                dpTable[i][j] = dpTable[i - 1][j];
            } else {
                dpTable[i][j] = max(dpTable[i - 1][j], items[i - 1].value + dpTable[i - 1][j - items[i - 1].weight]);
            }
        }
    }

    // 根据动态规划表格找出解集
    struct Item* objectInPack = (struct Item*)malloc(itemCount * sizeof(struct Item));
    int i = itemCount;
    int j = packCapacity;
    int objectCount = 0;
    while (i > 0 && j > 0) {
        if (dpTable[i][j] != dpTable[i - 1][j]) {
            objectInPack[objectCount++] = items[i - 1];
            j -= items[i - 1].weight;
        }
        i--;
    }

    // 释放动态规划表格内存
    for (int i = 0; i <= itemCount; i++) {
        free(dpTable[i]);
    }
    free(dpTable);

    return objectInPack;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    struct Item items[] = {
        {"吉他", 1500, 1},
        {"笔记本电脑", 2000, 3},
        {"音箱", 3000, 4},
        {"IPhone", 2000, 1}
    };
    int itemCount = sizeof(items) / sizeof(items[0]);

    int packCapacity = 4;

    struct Item* objectInPack = stealObject(packCapacity, items, itemCount);

    int maxValue = 0;

    printf("偷了如下物品：\n");
    for (int i = 0; i < itemCount; ++i) {
        maxValue += objectInPack[i].value;
        printf("%s\n", objectInPack[i].name);
    }

    printf("总价值：%d\n", maxValue);

    // 释放内存
    free(objectInPack);

    return 0;
}