首页 > 代码库 > 一个问题带来的学习
一个问题带来的学习
【故事】
地主是个胆小的人，而且考虑了各种情况还是决定要给出这30单位的粮食。就叫众人看看如何选择粮仓，损失最少。最后的结果就是：把各个粮仓的粮食计算一下，选择刚好满足30单位的粮仓就可以了。众人纷纷使出了自己灵活的大脑，快速的计算起来了。大家想了半天，也还没拿出最终的方案。地主这个时候看到管家这悠闲的思索着，便问道：你有何良策？管家笑道：要满足山大王30单位的粮食，也就是选择几座粮仓的粮食之和刚好满足30，直接去计算不免有点乏力。不过可以从相反的角度来思考：我们的目的是要使得交出去的量最小。那么从相反的角度来说，如果我们去找那些能够让自己留下来的粮食最多的粮仓，那么剩下来的粮仓也就是要交给山大王的。（大赞建凡）
在最终选择了粮仓之后啊，突然有人给地主送来一匹良驹，据说日行千里，背驮万顷。地主大喜，命令去选择好的粮去把多余30的粮食给偷偷运回来。可是去哪一座粮仓就疑惑了，如果用良驹去跑所有选择的粮仓查看是否可以，时间上根本来不及。地主问管家：选择的粮仓中是不是肯定有一座是大于这个多余的粮食的。管家想了想，说道：我不敢跟你直接说这个结果，但是我可以这么跟您说，假设这些选择的粮仓中所有的粮食都小于多余的，如此如此，结果根本不可能，所以肯定有一个是大于多余的量的，因此查一下各个粮仓的剩余量，也就可以了。
------------------------------------------------
【思考】
抽象出来两个问题：
1. 有一个序列X = {X1, X2, ..., Xn}。对于X的任意子集X′ = {xi | xi∈X}，求Min(ΣX′) > Y（Y是一个阈值）。也就是就一个子序列，满足两个条件：
（1）子序列之和要大于Y
（2）满足条件（1）中和最小的子集
2. 对于上面求出来的子序列Xk = {xi | xi∈X}，设ΣXk = S， R = S - Y。证明肯定存在一个xi（xi∈Xk）满足：xi >= R。
你也先别看，思考一下有什么好的办法去解决这个问题，高手有什么别的建议或者更好的办法也希望能分享给小弟，多谢！^_^
【思路】
1. 问题1
整体的思路如下：
（1）想到背包问题，但是有一点不一样。背包问题是刚好小于背包的大小，而这题是大于。但是还是非常符合动态规划的子问题重叠，但是一直没转换成动态规划解题。
（2）分而治之。朋友的思路。
（3）第二天一早，朋友就给我电话，说可以这样：背包问题是求给定大小下的最大价值问题，此题反过来思考就是一个背包问题，把序列和减去阈值，然后求满足这个容量的背包问题，最后没有被选中的就是此题的结果！直接大赞啊！^_^
2. 问题2
想了一会，然后想到反证法，也就很快看到结果了。毫无疑虑的往下写代码了。
证明：
设x1+x2+...+xn >= Y，并且x1+x2+...+xn-xi < Y(i=1,n), R = x1+x2+...+xn - Y
假设不存在一个xi 满足xi >= R,即所有的xi(i=1,n), 都有xi > R
因为x1+x2+...+xn-xi < Y
所以x1+x2+...+xn < Y+xi < Y+R
与x1+x2+...+xn = Y+R矛盾
所以证明成立！
【结果】
逻辑没有问题了，问题也就迎仍而解了！还是贴一段代码（参考网上改动了一点内容）
typedef struct _tagLYGoods{ int nValue; int nWeight;}LYGoods;int LYMax(int a, int b){ return ((a > b) ? a : b);}int LYPrintPack(int **c, LYGoods *A, int nItem, int nSize, std::vector<int> &vecRet){ int *Ret = new int[nItem]; for (int i = 0; i < nItem; i++) Ret[i] = 0; for (int i = nItem; i > 0; i--) { if (c[i][nSize] > c[i - 1][nSize]) { Ret[i - 1] = 1; nSize -= A[i - 1].nWeight; } } cout << "PrintPack: " << endl; for (int j = 0; j < nItem; j++) { if (Ret[j] == 0) vecRet.push_back(j); cout << Ret[j] << ", " << A[j].nWeight << ";"; } cout << endl; delete[] Ret; return true;}int LYPack(LYGoods *A, int nItem, int nSize, std::vector<int> &vecRet){int **MN = new int*[nItem + 1]();//定义一维动态数组 for (int i = 0; i<nItem + 1; i++)//用循环令一维数组变成二维 { MN[i] = new int[nSize + 1]; } int nMax = 0; for (int i = 0; i < nItem; i++) for (int j = 0; j < nSize; j++) MN[i][j] = 0; for (int i = 1; i <= nItem; i++) { for (int j = 1; j <= nSize; j++) { if (j < A[i - 1].nWeight) { MN[i][j] = MN[i - 1][j]; } else { MN[i][j] = LYMax(MN[i - 1][j], MN[i - 1][j - A[i - 1].nWeight] + A[i - 1].nValue); } } } LYPrintPack(MN, A, nItem, nSize, vecRet); int nRet = MN[nItem][nSize]; for (int i = 0; i<nItem + 1; i++) { delete[] MN[i]; } return nRet;}
（1）结果：
序列：2, 11, 15, 20, 32, 阈值：31
得到的结果是：11, 20
（2）随机结果：
【总结】
1. 很高兴碰到一个这样的问题，而且静下心来去解决
2. 交流是很重要的，比一个人学习的收益要大很多^_^
3. 动态规划还真是没有搞懂！继续学习！
一个问题带来的学习