昨天终于实现了“0/1背包问题”的算法，并且将搜狐2012年的那道题当做“0/1”背包问题来解，也获得了成功。在这个过程中，我发现了个问题：原来“0/1背包问题”的算法也是通过试探和回溯来实现的（因为我的能力现在有限，不能将算法的整个过程看到底，所以还没能确定算法里是否有回溯，我偏向于有）。那本《数据结构》中提到：“回溯法也是设计递归过程的一种重要方法，它的求解过程实质上是一个先序遍历一棵‘状态树’的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历过程中，但如果认识到这点，很多问题的递归过程设计也就迎刃而解了”。
但是，“0/1背包问题”与“求含N个元素的集合的幂集”有个重大的不同：“0/1背包问题”是有条件限制的。这个限制条件是：背包的容量，或者成为承重量最大不超过M。这样当试探过程中出现的状态和问题的限制条件矛盾时，便不再继续试探下去。
“0/1背包问题”的完整描述是：有一个背包，承重量为W；有N种物品，每种物品有且仅有1件，物品i的重量为wi，价格为pi；要求将物品放入包中，在包能承受的条件下，使包中的物品价值达到最大。很显然，物品i要么被放入包中，要么不被放入包中，所以称该问题为“0/1背包问题”。如果大家觉得我描述得根本不清楚，大家可以自己到网上查，我是通过*了解“0/1”背包问题的，网址如下：http://zh.wikipedia.org/zh/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98。
怎样用“0/1背包问题”的算法来解搜狐的这道题呢？很多人都提出了自己的想法，其中，chinaunix论坛上的网友koolcoy(娶妻求贤)也给出了自己的算法，虽然概括，但很简单，很清晰。他提出的算法是：
第一步：找出和比M小的一组数，并求出这个和能取到的最大值；
第二步：找出和比M大的一组数，并求出这个和能取到的最小值；
第三步：比较第一步和第二步计算出的结果。
其中，第二步可以采用如下的方法来解：求出M相应于这N个数的总和sumN的补数complementaryM，找出和比complementaryM小的一组数，并使这组数的和complementaryM取得最大值，那么这N个数中，除去这组数，剩下的那组数的和便比M大，同时最小。
还有一个问题，就是这组数是作为物品的价值呢，还是重量呢？因为M是个界限，所以M相当于包的承重量，而这组数中每个元素的类型都与M相同，所以这组数可以作为物品的重量。那么物品的价格这个角色有谁来担当呢？因为“0/1背包问题”求的是价值的最大值，本题求的是最接近M，所以价值还得由这组数来担当，即该问题中物品的价值和它的重量在数量上是相等的（单位当然不等了~~）。
说了这么多，可能还是没有说明白，还是那句话，大家可以到网上自己查找~~。
源代码如下，请指正：“
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#define Debug_Enable 0
#define Solve_TheQuestion 1
typedef struct {
double w;
double v;
} Item;
/*
全局变量默认值总是0.
*/
const int MaxCnt = 100; // 本程序最多处理100种(1个/种)物品
Item items[MaxCnt];
int cnt = 0; // 物品数量
void FindMax(int i, double curW, double tolV, const double limitW, double &maxV, int *
workVector, int * option)
{
int k = 0;
if (curW+items[i].w <= limitW) // 包含物品i是可接受的
{
workVector[i] = 1; // 将物品i包含在当前方案中
if (i < cnt-1)
{
FindMax(i+1, curW+items[i].w, tolV, limitW, maxV, workVector, option);
}
else
{
// 又一个完整方案, 且比前面的方案好:
for (k=0; k<cnt; ++k)
{
option[k] = workVector[k];
}
maxV = tolV;
}
workVector[i] = 0; // 恢复物品i不包含状态
/*
虽然像算法6.14, 但此算法应该没有回溯吧~~, SLL, 2011-11-15
此算法没有回溯? SLL, 2011-11-16
*/
}
if (tolV-items[i].v > maxV) // 不包含物品i仅是可考虑的
{
if (i < cnt-1)
{
FindMax(i+1, curW, tolV-items[i].v, limitW, maxV, workVector, option);
}
else
{
for (k=0; k<cnt; ++k)
{
option[k] = workVector[k];
}
maxV = tolV - items[i].v;
}
}
}
int main()
{
double totalW = 0.0;
double totalV = 0.0; // 本方案可能达到的总价值
double maxV1 = 0.0; // 本方案所达到的总价值
double maxV2 = 0.0;
double limitW = 0.0; // 包的最大容量
int k = 0; // 循环变量
double w = 0.0;
double v = 0.0;
cout << "Input the total number(<=100): ";
cin >> cnt;
while (cnt > 100)
{
cout << "The total number is too large! Please<=100: ";
cin >> cnt;
}
int * pOption1 = new int[cnt]; // 以0/1序列的形式, 标记方案中选择的与舍弃的物品
if (!pOption1)
{
cout << "Memory Error!" << endl;
exit(1);
}
int * pOption2 = new int[cnt];
if (!pOption2)
{
cout << "Memory Error!" << endl;
exit(1);
}
int * pWorkVector = new int[cnt];
if (!pWorkVector)
{
cout << "Memory Error!" << endl;
exit(1);
}
memset(pOption1, 0, sizeof(int) * cnt);
memset(pOption2, 0, sizeof(int) * cnt);
memset(pWorkVector, 0, sizeof(int) * cnt);
cout << "Input the value of the elements: ";
for (k=0; k<cnt; ++k)
{
cin >> w;
v = w;
items[k].w = w;
items[k].v = v;
totalW += items[k].w;
totalV += items[k].v;
}
cout << "Input the target: ";
cin >> limitW;
FindMax(0, 0.0, totalV, limitW, maxV1, pWorkVector, pOption1);
int complementaryLimW = totalW - limitW;
FindMax(0, 0.0, totalV, complementaryLimW, maxV2, pWorkVector, pOption2);
int complementaryMinV = totalV - maxV2;
if (abs(maxV1-limitW) < abs(complementaryLimW-limitW))
{
cout << "the nearest value with " << limitW << " is: " << maxV1 << '\n'
<< "the elements are: ";
for (k=0; k<cnt; ++k)
{
if (pOption1[k])
{
cout << items[k].w << ' ';
}
}
cout << endl;
}
else
{
cout << "the nearest value with " << limitW << " is: " << complementaryMinV << '\n'
<< "the elements are: ";
for (k=0; k<cnt; ++k)
{
if (!pOption2[k])
{
cout << items[k].w << ' ';
}
}
cout << endl;
}
if (pWorkVector)
{
delete [] pWorkVector;
pWorkVector = NULL;
}
if (pOption2)
{
delete [] pOption2;
pOption2 = NULL;
}
if (pOption1)
{
delete [] pOption1;
pOption1 = NULL;
}
return 0;
}
”。