算法设计 教材_算法设计的例子_小魏的修行路

  本文关键词：算法设计，由笔耕文化传播整理发布。

根据实例，可以理出追踪解的思路，代码如下：

void TrackSolution(int v[N],int w[N],int tagi[][B+1]){ //x[i-1]标记第i件物品的件数 int x[N]; for(int i=0;i<N;i++) x[i]=0; int y=B,j=tagi[N][B]; while (tagi[j][y]!=0){ j=tagi[j][y]; //标记函数最下角ik(y)标记的物品取一件 x[j-1]=1; y=y-w[j-1]; while (tagi[j][y]==j){ y=y-w[j]; x[j-1]=x[j-1]+1; } } }运行结果：

背包问题是很经典的动态规划问题，很多问题都是背包的变种，比如下面两个题目：

第一个题目其实就是0-1背包问题，即看做价值和重量相等（都为ai）的物品装入背包，每件物品最多选1件，总重不能超过K，总价值最大的问题。设Fk(y)表示只允许前k个下载请求，最大带宽不超过y时利用最大限度的带宽数。递推关系和边界条件如下：

注意0-1背包和背包问题的递推关系主要区别是：当选择第k件物品时，Fk(y)表示为Fk-1(y-wk)+vk，而非Fk(y-wk)+vk，即只能在前k-1件物品里继续选择。另外F1(y)的边界函数也不同。

至于第二个题目，其实就是使得一条加工线上的加工时间不超过T/2时加工时间尽可能大的问题，和第一个问题是一样的。

代码下载：

参考资料：屈婉玲 刘田等 《算法设计与分析》

  本文关键词：算法设计，由笔耕文化传播整理发布。