编辑代码

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