题0-1背包问题：
• 第一个式子是不装入物品i，也可能物品i无 法装入，背包的容量不变，转化为前i+1个 物品放与容量为j的背包中
•        第二个式子装入物品i则新增加价值vi，但容 量变位j-w，对于最后一个物品n，若j》=w
p(i，j)  max( p(i 1，j)，p(i 1，j  wi )  vi }        j  wi
 p(i 1，j)        0   j  wi
•        题：最长单调子系列
• 辅助数组b表示以a为结尾的最长递增子 序列长度，则序列L的最长递增子序列的长 度：max {b}
•        B[1]=1;
•        B=max{b[k]}+1
int LIS_n2(int n)        //教材上这一句丢掉了
{
int b[NUM]={0};        //辅助数组b
int i,j; b[1] = 1;
int max = 0;        //数组b的最大值
for (i=2;i<=n; i++)
{
int k = 0;
for (j=1; j<i; j++)        //0~i-1之间，b的最大值
if (a[j]<=a && k<b[j]) k=b[j]; b = k+1;
if (max<b) max=b;
}
return max;
}
•        贪心选择性质是指所求问题的整体最优解可以通 过一系列局部最优的选择，即贪心选择来达到
Greedy(A)
{
S={ };        //初始解集合为空集
while (not solution(S))        //集合S没有构成问题的一个解
{
x = select(A);        //在候选集合A中做贪心选择
if feasible(S, x)        //判断集合S中加入x后的解是否
可行
S = S+{x};
A = A-{x};
}
return S;
｝
（一）经典的算法：贪心算法背包
问题
double knapsack(int n, bag a[], double c)
{
double cleft = c; int i = 0;
double b = 0;
while(i<n && a.w<=cleft)
{
cleft -= a.w;
b += a.v;
//物品原先的序号是a.index，全部装入背包
a[a.index].x = 1.0; i++;
}
if (i<n)        {
a[a.index].x = 1.0*cleft/a.w;
b += a[a.index].x*a.v;
}
return b;
}
•        令cw(i)表示目前搜索到第i层已经装入背包的 物品总重量，即部分解(x1, x2 , …, xi)的重量：
i
cw(i)   x j wj
j1
•        对于左子树， xi =1 ，其约束函数为：
constraint (i)  cw(i  1)  wi
•        若constraint(i)＞W，则停止搜索左子树，否
则继续搜索。
•        对于右子树，为了提高搜索效率，采用上界函数
Bound(i)剪枝。
•        令cv(i)表示目前到第i层结点已经装入背包的物品
价值：cv(i)   x jv j
j1

r(i) 

n
v j
ji1
•        令r(i)表示剩余物品的总价值：
Bound (i)

 cv(i) 

r(i)
•        则限界函数Bound(i)为：
#define NUM 100
int c;        //背包的容量
int n;        //物品的数量
int cw;        //当前重量
int cv;        //当前价值
int bestv;        //当前最优价值
//描述每个物品的数据结构 struct Object{
int w;        //物品的重量
int v;        //物品的价值
double d;        //物品的单位重量价值比
//物品的数组

void backtrack(int i)
{
//到达叶子结点时，更新最优值 if (i+1>n) {bestv = cv; return;}
//进入左子树搜索 if (cw+Q.w<=c)
{
cw += Q.w;
cv += Q.v; backtrack(i+1); cw -= Q.w;
cv -= Q.v;
}
//进入右子树搜索
if (Bound(i+1)>bestv) backtrack(i+1);

int cleft = c-cw;        //背包剩余的容量 int b = cv;                //上界
//尽量装满背包
while (i<n && Q.w<=cleft)
{
cleft -= Q.w;
b += Q.v; i++;
}
//剩余的部分空间也装满
if (i<n) b += 1.0*cleft*Q.v/Q.w; return b;
}
•        从活结点表中选择下一个活结点作为新的扩展 结点，分支限界算法通常可以分为两种形式：
1.FIFO（First In First Out）分支限界算法
–按照先进先出（FIFO）原则选择下一个活结点作为 扩展结点，即从活结点表中取出结点的顺序与加入结 点的顺序相同。
2.最小耗费或最大收益分支限界算法
–在这种情况下，每个结点都有一个耗费或收益。
–根据问题的需要，可能是要查找一个具有最小耗费 的解，或者是查找一个具有最大收益的解。
•        限界函数：
•        求max维护或节点，从活节点选择一个节点 作为扩展节点，对扩展节点的每个分支i， 计算其上界值，若当前最大的目标函数值 best不小于bound（i）不会放入活节点，否 则放入，所以若bound（i）《=best表示正 在搜索的节点i为死节点减掉

预测未来最好的方法就是去创造未来。

Don't try so hard, the best things come when you least expect them to. 不要着急，最好的总会在最不经意的时候出现。