编辑代码

#include <iostream>
using namespace std;
struct good
{
	string name;
	int weight;
	int value;
	good(string n, int w, int v)
	{
		name = n;
		weight = w;
		value = v;
	}
	good()
	{
		name = "0";
		weight = 0;
	}
};
int Result(int packcapacity, good* goods, int goodcount)
{
	int minweight = goods[0].weight;
	for (int i = 1; i < goodcount; i++)
	{
		if (minweight > goods[i].weight)
		{
			minweight = goods[i].weight;
		}
	}
	if (packcapacity < minweight)
	{
		cout << "背包的容量：" << packcapacity << "小于要放入的所有物品的最小重量：" << minweight << endl;
		return 0;
	}
	int** dpArray = new int* [goodcount]();
	int weightcount = packcapacity + 1;
	for (int i = 0; i < goodcount; i++)
	{
		dpArray[i] = new int[weightcount];
	}
	for (int i = 0; i < goodcount; i++)
	{
		int putweight = goods[i].weight;
		int putvalue = goods[i].value;
		for (int w = minweight; w < weightcount; w++)
		{
			int lastvalue = 0;
			if (i > 0)
			{
				lastvalue = dpArray[i - 1][w];
			}
			int nowvalue = 0;
			if (w >= putweight)
			{
				nowvalue = putweight;
			}
			if (w > putweight && i > 0)
			{
				nowvalue += dpArray[i - 1][w - putweight];
			}
			int maxvalue = lastvalue;
			if (lastvalue < nowvalue)
			{
				maxvalue = nowvalue;
			}
			dpArray[i][w] = maxvalue;
		}
	}
	int MaxValue = dpArray[goodcount - 1][weightcount - 1];
	for (int i = 0; i < goodcount; ++i)
	{
		delete[] dpArray[i];
	}
	delete[] dpArray;
	return MaxValue;
}
int main()
{
	good goods[] = {
	   good("A", 6, 5),
	   good("B", 5, 3),
	   good("C", 4, 5),
	   good("D", 2, 3),
	   good("E", 1, 2),
	};
	int packcapacity = 10;
	int goodcount = sizeof(goods) / sizeof(good);
	int MaxValue = 0;
	MaxValue = Result(packcapacity, goods, goodcount);
	if (MaxValue > 0)
	{
		cout << "最大的价值是： " << MaxValue << endl;
	}
}