编辑代码

#include <iostream>
using namespace std;
struct Item {
	string name;
	int weight;
	int value;
	Item *next;

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

	Item() {
		name = "";
		weight = 0;
		value = 0;
		next = NULL;
	}

	Item(Item *item) {
		name = item->name;
		weight = item->weight;
		value = item->value;
		next = item->next;
	}
};

struct Result {
	int value;
	Item *head;

	Result() {
		value = 0;
		head = new Item();
	}

	Result(Result *result) {
		value = result->value;
		head = new Item();
		head->next = result->head->next;
	}
};

Result* 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 NULL;
	}


	//创建表格，横轴是物品，纵轴是包能放入的物品的重量
	Result** dpArray = new Result*[itemCount]();//常来记录每一行对应的数组空间

	int weightCount = packCapacity + 1;

	for (int i = 0; i < itemCount; ++i) {
		dpArray[i] = new Result[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].value;
			}

			// 记录放入当前物品的情况下，放入背包物品能够达到的最大价值
			int curTotalValue = 0;

			// 如果当前物品能够放入背包，记录下物品的价值
			if (w >= curWeight) {
				curTotalValue = curValue;
			}
			// 如果放入当前物品后背包还能放入其它物品，且确实还有其它物品，加上剩余的小背包能够放入物品的最大价值
			if ( w > curWeight && i > 0 ) {
				curTotalValue += dpArray[i-1][w - curWeight].value;
				dpArray[i][w].head->next = dpArray[i-1][w - curWeight].head->next;
			}

			// 找出放入当前物品和不放入当前物品情况下，放入背包的物品能够达到的最大价值
			int maxTotalValue = preTotalValue;

			if (maxTotalValue < curTotalValue) {
				maxTotalValue = curTotalValue;
				items[i].next = dpArray[i][w].head->next;
				dpArray[i][w].head->next = new Item(&items[i]);
			} else {
				dpArray[i][w].head->next = dpArray[i - 1][w].head->next;
			}

			// 记录下放入当前物品后，能够放w磅物品的背包能够放入物品的最大价值
			dpArray[i][w].value = maxTotalValue;

		}
	}

	//记录下最终的最大结果
	Result *result = new Result(&dpArray[itemCount - 1][weightCount - 1]);

	for (int i = 0; i < itemCount; ++i) {
		for (int j = 0; j < weightCount; ++j) {
			delete dpArray[i][j].head;
		}
		delete [] dpArray[i];
	}

	delete [] dpArray;

	return result;
}

int main()
{
	int days = 4;
	Item items[] = {
		Item("故宫", 1, 7),
		Item("颐和园", 2, 8),
		Item("长城", 3, 9),
		Item("长城", 1, 6)
	};
	int itemCount = sizeof(items)/sizeof(Item);
	Result* result = NULL;

	result = backpack(days, items, itemCount);

	if (result->value > 0) {
		cout << "Max value is " << result->value << endl;
		Item *item = result->head->next;
		Item * prev = NULL;
		cout << "Scenic spots are ";
		while ( item != NULL) {
			cout << item->name << " ";
			prev = item;
			item = item->next;
			delete prev;
		}
		cout << endl;
	}

	delete result->head;
	delete result;
}