加载中…GKnapSack（跳跃点法解 0-1 背包问题）
(2015-10-08 14:49:52)
标签：
it动规 |
分类： ACM |
对于 0-1 背包问题，DP的解法很普遍。还有一种“跳跃点”的解法，该方法的提出，是根据背包求解过程中的记录表
v（i，j）的函数性特点而来的。（v（i，j）表记录的是前 i 种物品，达到总重量 j 时的最大利益）
int w , v;
Data(int nw = 0 , int nv
= 0):w(nw) , v(nv){}
Data operator +(const
Data& r)const
{
return Data(w+r.w , v+r.v);
}
bool operator ==(const
Data& r)const
{
return (w==r.w) && (v==r.v);
}
int i , j;
bool x[N+2];
for(i = n ; i >= 1 ;
--i)
{
x[i] = false;
for(j = head[i]-1 ; j >= head[i-1] ;
--j)
{
if(table[j]+goods[i] == eState && (table[j].w != 0 ||
!j))
{
s.push(i);
eState = table[j];
break;
}
}
}
int i , k , j , l , r ,
next;
Data temp;
head[0] = 0;
table[0] = Data(0 ,
0);
l = r = 0;
next = 1;
head[1] = 1;
for(i = 1 ; i <= n ;
++i)
{
k = l;
for(j = l ; j <= r ; ++j)
{
if(table[j].w+goods[i].w > c)
break;
temp =
table[j]+goods[i];
while(k<=r && table[k].w
{
table[next] = table[k];
++next;
++k;
}
if(k<=r
&& table[k].w==temp.w)
{
temp.v = max(temp.v ,
table[k].v);
++k;
}
if(temp.v
> table[next-1].v)
{
table[next] = temp;
++next;
}
while(k<=r && table[k].v<=table[next-1].v)
++k;
}
while(k <= r)
{
table[next] = table[k];
++next;
++k;
}
l = r+1;
r = next-1;
head[i+1] = next;
}
traceBack(table[next-1]);
return
table[next-1].v;
int i;
scanf("%d%d" , &n ,
&c);
// the number of goods
and the capcity of the bag
for(i = 1 ; i <= n ;
++i)
{
scanf("%d%d" , &goods[i].w ,
&goods[i].v);
// the weight and the value of goods i
}
printf("\n%d\n" ,
GKnapSack());
for(i = 0 ; i <= n ;
++i)
{
printf("%d : " , i);
for(int j = head[i] ; j < head[i+1] ;
++j)
{
printf("%d
%d ; " , table[j].w , table[j].v);
}
printf("\n");
}
printf("\n");
while(!s.empty())
{
printf("%d " , s.top());
s.pop();
}
printf("\n");
return 0;
可以Dp 求解一下，然后打印一下表进行观察，也可以根据这个求解原理，可以很自然的想到，v（i，j）的函值， 当 i
确定时，这是一个关于 j
的非递减函数，且由“跳跃点”将函数分段儿了，类似于上取整/下取整的函数图像，以跳跃点为分界非递减的一段一段儿“平”的函数图像。在求解过程中，每一个
i 都会有对应着一个这样的函数图像，并且最后一个求解时，刚好，最高的跳跃点对应的函数线即为解。
根据 v（i，j） = max（v（i-1，j） ， v（i-1，j-w[i]）+v[i]），即对于一个函数图像
v（i）是可以有其“前驱” v（i-1）得出的。求解过程是
由前导后的，并且根据公式，本质上，新的跳跃点，新的函数图像就是在已有图像的基础上得出的（即 i 状态本身就是在 i-1
的状态下得出的）。实际求解过程 ：（过程中需要打表记录，表中的数据记录是一个structure，即占用 w 时最大价值为 v，过程中以
i （前 i 种物品为状态标记量））
1.初始化 p（0）<0 , 0 > // 边界
2.由 p（i-1）[ v ( i -1 , j ) 的状态图 ] 得到 q（i-1）[ v ( i - 1 , j -
w[i] ) + v[i] 的状态图 ] . 只需要在 p（i-1）的基础上 + （wi，vi）得到新的跳跃点即可。
3. p（i-1）并上 q（i-1）在减去必然不合法的点（同 w 下 v 非最大的点）即为 p（i）
上述即为求解过程，迭代实现即可。
代码在实际实现的过程中，把一维表 table 用作了 二维表，通过 head[ ]
数组的划分，达到了二维表的效果，head[ i ] 表示 p（i）在表中的首元素位置。同时借助 p（i-1）导 p（i）的时候，用 l
，r 作为指针，卡在了p（i-1）的左右作为边界，next是p（i）要填写的位置，最初时 next 为 p（i）的head
位置。
先在 p（i-1）的元素 j 上得到一个新状态，然后 w 小于它的不受影响，直接搬，w 等于它的，对 v 取大更，w
大于它的，根据 v 值直接pass 掉 不合法的点（w 大但 v 小于前边的），同时，出现了新状态往里写的时候，也要注意，w 大 v
也大时才合法，才可以往里写，反之直接扔掉。（在跳跃点函数图像中，保留的的是 max ，即p（i-1），q（i-1）俩函数图取 max
的合图）
记录好表之后，从终态开始往回倒找解路径即可。
示例代码 ：
#include
#include
#include
#include
#include
using namespace std;
const int N = 1e4 , M = 1e6;
struct Data
{
};
int head[N+5];
Data goods[N] , table[M];
stack s;
int n , c;
// trace back to find the solution vector x[1……n]
void traceBack(Data eState)
{
}
// jump points' method to slove the 0-1 bag's problem
int GKnapSack()
{
}
int main()
{
}
喜欢
0
赠金笔
前一篇：回溯法一般性框架示例代码
后一篇：最优二叉查找树的构造