由此可见，在递归地由表p[i+1]计算表p[i]时，可先由p[i+1]计算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳跃点得到表p[i]。
例：n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。跳跃点的计算过程如下：
初始时p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6] (w5,v5)={(4,6)}。 p[5]={(0,0),(4,6)}。q[5]=p[5] (w4,v4)={(5,4),(9,10)}。从跳跃点集p[5]与q[5]的并集p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到
p[4]={(0,0),(4,6),(9,10)}
q[4]=p[4] (6，5)={(6，5)，(10，11)}
p[3]={(0，0)，(4，6)，(9，10)，(10，11)}
q[3]=p[3] (2，3)={(2，3)，(6，9)}
p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}
q[2]=p[2] (2，6)={(2，6)，(4，9)，(6，12)，(8，15)}
p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}
p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。
具体代码实现如下：
[cpp]
//3d10-2 动态规划 背包问题 跳跃点优化
#include "stdafx.h"
#include
using namespace std;
const int N = 4;
template
int Knapsack(int n,Type c,Type v[],Type w[],int **p,int x[]);
template
void Traceback(int n,Type w[],Type v[],Type **p,int *head,int x[]);
int main()
{
int c=8;
int v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下标从1开始
int x[N+1];
int **p = new int *[50];
for(int i=0;i<50;i++)
{
p[i] = new int[2];
}
cout<<"待装物品重量分别为："<
for(int i=1; i<=N; i++)
{
cout<
}
cout<
cout<<"待装物品价值分别为："<
for(int i=1; i<=N; i++)
{
cout<
}
cout<
cout<<"背包能装的最大价值为："<
cout<<"背包装下的物品编号为："<
for(int i=1; i<=N; i++)
{
if(x[i]==1)
{
cout<
}
}
cout<
return 0;
for(int i=0;i<50;i++)
{
delete p[i];
}
delete[] p;
}
template
int Knapsack(int n,Type c,Type v[],Type w[],int **p,int x[])
{
int *head = new int[n+2];
head[n+1]=0;
p[0][0]=0;//p[][0]存储物品重量
p[0][1]=0;//p[][1]存储物品价值，物品n的跳跃点（0，0）
// left 指向p[i+1]的第一个跳跃点，right指向最后一个
//拿书上的例子来说，若计算p[3]=0;则left指向p[4]的第一跳跃点（0 0）right指向（9,10）
int left = 0,right = 0,next = 1;//next即下一个跳跃点要存放的位置
head[n]=1;//head[n]用来指向第n个物品第一个跳跃点的位置
for(int i=n; i>=1; i--)
{
int k = left;//k指向p[ ]中跳跃点,移动k来判断p[]与p[]+（w v）中的受控点
for(int j=left; j<=right; j++)
{
if(p[j][0]+w[i]>c) break;//剩余的空间不能再装入i，退出for循环;
Type y = p[j][0] + w[i],m = p[j][1] + v[i];//计算p[ ]+（w v）
//若p[k][0]较小则(p[k][0] p[k][1])一定不是受控点，将其作为p[i]的跳跃点存储
while(k<=right && p[k][0]
{
p[next][0]=p[k][0];
p[next++][1]=p[k++][1];
}
//如果 p[k][0]==y而m
if(k<=right && p[k][0]==y)
{
if(m
{
m=p[k][1];
}
k++;
}
// 若p[k][0]>=y且m> =p[k][1],判断是不是当前i的最后一个跳跃点的受控点
//若不是则为i的跳跃点存储
if(m>p[next-1][1])
{
p[next][0]=y;
p[next++][1]=m;
}
//若是，则对下一个元素进行判断。
while(k<=right && p[k][1]<=p[next-1][1])
{
k++;
}
}
while(k<=right)
{
p[next][0]=p[k][0];
p[next++][1]=p[k++][1];//将i+1剩下的跳跃点作为做为i的跳跃点存储
}
left = right + 1;
right = next - 1;
// 第i-1个物品第一个跳跃点的位置 head[0]指第0个物品第一个跳跃点的位置
head[i-1] = next;
}
Traceba