编辑代码

#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<< " 背包的最大承重： " 
            << packCapacity << " 小于物品中重量最小的： " 
            << minWeight << endl;
        return -1;
    }
    int weightCount = packCapacity + 1;// 创建表格，横轴是物品，纵轴是包能放入的物品的重量 2
    int** dpArray = new int*[itemCount]();
    for (int i = 0; i < itemCount; ++i)
	{
        dpArray[i] = new int[weightCount];
    }
    for (int i = 0; i < itemCount; ++i)// 填充表格 1
    {
        
        int curWeight = items[i].weight;// 记录放入背包物品的重量和价值 0
        int curValue = items[i].value;
        for (int w = minWeight; w < weightCount; ++w)
        {
            
            int preTotalValue= 0;// 记录不放入当前物品的情况下，放入背包物品能够达到的最大价值 5
            if (i > 0)
			{
                preTotalValue = dpArray[i - 1][w];
            }
            int curTotalValue = 0;// 记录放入当前物品的情况下，放入背包物品能够达到的最大价值 2
            if (w >= curWeight)// 如果当前物品能够放入背包，记录下物品的价值 0
			{
                curTotalValue = curValue;
            }
            if ( w > curWeight && i > 0 )// 如果放入当前物品后背包还能放入其它物品，且确实还有其它物品，加上剩余的小背包能够放入物品的最大价值 5
			{
                curTotalValue += dpArray[i-1][w - curWeight];
            }
            int maxTotalValue = preTotalValue;// 找出放入当前物品和不放入当前物品情况下，放入背包的物品能够达到的最大价值 4
            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("第一件", 6, 5),
		Item("第二件", 5, 3),
		Item("第三件", 4, 5),
        Item("第四件", 2, 3),
		Item("第五件", 1, 1),
    };
    int itemCount = sizeof(items)/sizeof(Item);
    int maxValue = 0;
    maxValue = backpack(packCapacity, items, itemCount);
    if (maxValue > 0)
	{
        cout << "Max value is " << maxValue << endl;
    }
}