#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;
}
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);
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(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;
}