编辑代码

#include <iostream>
using namespace std;

struct Item {
    string name;
    int weight;
    int value;

    Item(string n, int w, int v) {
        name = n;
        weight = w;
        value = v;
    }

    Item() {
        name = "";
        weight = 0;
        value = 0;
    }
};
int backpack(int packCapacity, 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) {
        cout << "The capacity of package " 
             << packCapacity << " is less than the minimum weight of items " 
             << minWeight << endl;
        return -1;
    }

    int weightCount = packCapacity + 1;
    int** dpArray = new int*[itemCount]();
    for (int i = 0; i < itemCount; ++i) {
        dpArray[i] = new int[weightCount];
    }

    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];
            }
             int curTotalValue = 0;
             if (w >= curWeight) {
                curTotalValue = curValue;
            }
            if ( w > curWeight && i > 0 ) {
                curTotalValue += dpArray[i-1][w - curWeight];
            }
            int maxTotalValue = preTotalValue;

            if (maxTotalValue < curTotalValue) {
                maxTotalValue = curTotalValue;
            }
            dpArray[i][w] = maxTotalValue;
        }    
    }
    int maxValue = dpArray[itemCount - 1][weightCount - 1];

    for (int i = 0; i < itemCount; i++) {
        delete [] dpArray[i];
    }
    delete [] dpArray;
    return maxValue;
}

int main() 
{
    int packCapacity = 10;
    Item items[] = {
        Item("物品1", 6, 5),
        Item("物品2", 5, 3),
        Item("物品3", 4, 5),
        Item("物品4", 2, 3),
        Item("物品5", 1, 2)
    };
    int itemCount = sizeof(items)/sizeof(Item);
    int maxValue = 0;
    maxValue = backpack(packCapacity, items, itemCount);
    if (maxValue > 0) {
        cout << "最大价值为： " << maxValue << endl;
    }    
}