The Dropbox Diet之动态规划

在Dropbox看招聘要求时，发现他们还有一个challenge页面，有三个算法题，让网友来challenge。第三题把题目看下来后的感觉很有意思。

题目

The Dropbox Diet

Of the boatload of perks Dropbox offers, the ones most threatening to our engineers' waistlines are the daily lunches, the fully-stocked drink fridge, and a full-length bar covered with every snack you could want. All of those calories add up. Luckily, the office is also well-equipped with ping-pong, a DDR machine, and a subsidized gym right across the street that can burn those calories right back off. Although we often don't, Dropboxers should choose the food they eat to counterbalance the activities they perform so that they don't end up with caloric deficit or excess.
Help us keep our caloric intake in check. You'll be given a list of activities and their caloric impact. Write a program that outputs the names of activities a Dropboxer should choose to partake in so that the sum of their caloric impact is zero. Once the activity is selected, it cannot be chosen again.

Input

Your program reads an integer N (1 <= N <= 50) from STDIN　representing the number of list items in the test input. The list is comprised of activities or food items and its respective calorie impact separated by a space, one pair per line. Activity names will use only lowercase ASCII letters and the dash (-) character.

Output

Output should be sent to stdout, one activity name per line, alphabetized. If there is no possible solution, the output should be no solution. If there are multiple solutions, your program can output any one of them.

Sample Input1

2

red-bull 140

coke 110

Sample Output1

no solution

Sample Input2

12

free-lunch 802

mixed-nuts 421

orange-juice 143

heavy-ddr-session -302

cheese-snacks 137

cookies 316

mexican-coke 150

dropballers-basketball -611

coding-six-hours -466

riding-scooter -42

rock-band -195

playing-drums -295

Sample Output2

coding-six-hours

cookies

mexican-coke

解析思路

题目意思很简单的，给定几种食物的名称及能量，要求选出一种搭配，使能量之和为零。问题转化为更一般的问题，给定几个数，问存不存在其中几个数的和为零。对于这种的题目，很容易想到的是去枚举一个序列的子序列，可以使用递归或二进制进行枚举，这种方法的一个优点就是容易理解，写起来也很快。但是，通常当序列长度达到25以后，时间效率基本上就无法承受，它是时间是指数级别，达到了2^25。
这里对于枚举效率低，主要是因为存在着大量的子问题重叠问题：
比如一个序列为：1　2　3　4　5　6　7　8　9　10
在前三个数中取[1, 2]和取[3]就重叠了,这里的重复计算达到2^7.
动态规划可通过保存一些子问题的状态，来避免这些重复计算，这样前三个数中取[1, 2] 和取[3]就可以合并成一个了。
这题到这大概思路已经有了，动态规划是避免不了了。仔细想想，又会发现还有一些问题：

问题1

序列有负数
序列有负数，这给用数组表示状态带来麻烦。
如果只有问题1，也就是只要判断能不能组合出某一个特定的数，可以想到用母函数，其实母函数就是动态规划的思想了。对于有负数的处理：

• 第一种方法是可以将正数和负数分开处理，处理负数时因为都为负数，就可将它们都变为正数来处理，这样的话，调用两次同个函数，再比较正数组成的和与负数组成的和中有没有相等的就可以知道存不存在和为零的序列了。
• 第二种方法是不分别处理，但进行平移，所有数都减去最小的负数，这样所有的数都处于正坐标上。再进行动态规划处理，最后判断有没有和等于最小负数的相反数，即把判断有没有为零的逻辑转换成判断经过平移后有没有最小负数的相反数。

从表面上来分析，第一种方法的时间效率要好一点，空间的话，都是一维，应该差不多的。

问题2

要输出选的是哪些元素
对于问题2，其实是比较麻烦的。这里组合数太多，所以通过枚举是无法达到要求的。这就需要用到矩阵来晰展示，用输入数组的下标来表示横坐标，可能取到的值来表示纵坐标。

比如一个序列为，[1　2　-4　3]，则矩阵形式为：其中列的范围为[-4, 6]，括号内为对应的数值。

下面就开始填充这个矩阵，从上往下一行行地填，代表前n个数可能组成的和。

填充规则(F or T)：
a. 当前行的数值列为T。代表前n个数中只选当前这个数。如Matrix[0][5]=T:

b. 如果前一行的某一列T，则下一行的对应列也为T。即若Matrix[i-1][j]=T，则Matrix[i][j]=T。前n-1个数可组成j，则前n个数肯定能组成j，即当前数不被选中。
c. 枚举前一行的所有值，若第j列为T，则下一行的 {j + (k)} 列为T；(k)为当前行的值。如Matrix[i-1][j]=T，则Matrix[i][j+(k)]=T。即代表当前数被选中。经过步骤b、c后

重复上面步骤直到将矩阵填满

矩阵中所有的T列代表整个序列可能组成的和。
对于步骤b，继承前一行的某些特性，即利用了子问题重叠特性。否则就需要遍历所有的先前行，才能确定当前行的某列值是否可达。利用继承后，只需遍历前一行就够了，这样就将循环层次下降了一层。
前面说过了，如果不需输出所选元素的话，可以利用母函数。母函数的特性在上面的矩阵中表现为当前行只与前一行有关，这样在实际做时就不需要矩阵了，只需要两个一维数组代表矩阵中的相邻行，由一个数组来生成另一个数组，进行滚动，将空间也降下一维。
下面就是输出所选序列了，这时利用矩阵就发挥其优势了。
从上面矩阵中确定和为0存在，因此从最后一行的0值列开始，即Martirx[3][4]开始往上查找，可能会有两条路：

path1: Martirx[3][4]-> Martirx[2][4] //不选最后一个数
path2: Martirx[3][4]-> Martirx[3][4-3] //有选最后一个数

如果两条都为T的话，随便一条就行；如果只有一个T，那就是它；两条路中肯定有一个T。这样递归处理回到第一行时，整个路径就出来了。

注意

最开始初始化Martirx第一行时，0值列没有初始化为T，理论上应该是为T的，因为当没选中第一个数时就为0。这里是考虑到后来的反向求路径，如果初始化为0，则要根据继承原则，整个矩阵的0值列都会为T。那么如果选则上面的path1，那最终得到的路径是空，所以没初始化为T就避免了这种情况。

代码示例

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{
	string name;
	int calorie;
}food[51];
int main()
{
// 	freopen("D:\in.txt", "r", stdin);
	int n, i, j;
	int min_negtive, sum_positive, range, success;
	while(cin >> n)
	{
		success = min_negtive = sum_positive = 0;
		for(i = 0; i < n; i++)
		{
			cin >> food[i].name >> food[i].calorie;
			if(food[i].calorie > 0)
			{
				sum_positive += food[i].calorie;
			}
			if(food[i].calorie < min_negtive)
			{
				min_negtive = food[i].calorie;
			}
		}
		min_negtive = -min_negtive;          //turn the negtive into positive
		range = sum_positive + min_negtive + 1;
		vector< vector<int> > vec_matrix(n, vector<int>(range, 0));
		vec_matrix[0][food[0].calorie + min_negtive] = 1;       //init the first row.
		for(i = 1; i < n && !success; i++)
		{
			vec_matrix[i][food[i].calorie + min_negtive] = 1;
			for(j = 0; j < range && !success; j++)
			{
				if(vec_matrix[i-1][j] == 1)
				{
					vec_matrix[i][j] = 1;         //inherit from former.
					int temp = j + food[i].calorie;
					if(temp < 0) 
						continue;
					if(temp >= range)
						break;           //no more test.
	 				vec_matrix[i][temp] = 1;
					if(temp == min_negtive)
					{
						success = 1;
					}
				}
			}
		}
		vector<string> vec_name;
		if(success)
		{
			i--;                // back to the last selected item.
			int temp = min_negtive;
			do{
				while(i >= 0 && vec_matrix[i][temp] == 1)
					i--;
				i++;			// back to the last selected item.
				vec_name.push_back(food[i].name);
				temp -= food[i].calorie;
				i--;
			}while(temp != min_negtive);
			sort(vec_name.begin(), vec_name.end());
			vector<string>::iterator iter = vec_name.begin();
			while(iter != vec_name.end())
			{
				cout << *iter << endl;
				iter++;
			}
		}
		else
		   cout << "no solution" << endl;
	}
	return 0;
}