(4)结果：
该算法主要时间用于单位价值排序，起时间复杂度为O(n*logn);(折半插入排序时间)
贪心装载时，耗时主要用于与剩余载重比较(w[ i]<=mm)时间为O(n)； 故该算法的时间复杂度为：O(n*logn+n)； 记为： O(n*logn)；
2、0-1背包装载问题：
(1)输入背包最大容量C：10 (2)输入物品个数n=3
(3)输入物品的重量：6 、 5 、 5
(4)输入各物品的价值p：56 、 23 、 43
（5）结果
3、棋盘覆盖问题：
设T(k)是覆盖一个2k×2k棋盘所需时间；则其满足如下递归方程：
O(1)k?1?T(k)???4T(k?1)?O(1)k?1解此递归方程得： T(k)＝O(4k)，故该算法的时间复杂度为O(4k)
六、结论
1、普通背包问题采用贪心算法实现。
首先计算每种物品单位重量的价值表p[i]/s[i]，然后，依据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。这样就使得目标函数增加最快，当最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。
2、0-1背包装载问题采用回溯算法实现。
设0/1背包问题的最优值为m( i, j )，即背包容量是j，可选择物品为i,i+1,…,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下：
m( i, j )= max{m( i+1, j ), m( i+1, j-wi)+vi} j?wi m(i+1,j)
vn j?wn m(n,j)=
0 0?k?wn
3、棋盘覆盖问题采用分治法实现。
在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘.
当k>0时,将2^k×2^k棋盘分割为4个2^k－1×2^k－1子棋盘,特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格.为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处。如下图–图（c）所示,这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而原问题转化为4个较小规模的棋盘覆盖问题.递归地使用这种分割,直至棋盘简化为1×1棋盘。 tr:棋盘左上角方格的行号 tc:棋盘左上角方格的列号 dr:特殊方格所在的行号 dc:特殊方格所在的列号 size:方形棋盘的边长
七、源程序
1、普通背包问题：
#include
void display(int &n,double &C,double s[M],double p[M]) { int i; s[0]=0;p[0]=0; cout<<\请输入物体数n:\ cin>>n; cout< cout<<\请输入背包总容量C:\ cin>>C; cout< cout<<\请输入各物体的大小或重量:\ for(i=1;i<=n;i++) cin>>s[i]; cout<<\请输入各物体的价值p:\ for(i=1;i<=n;i++) cin>>p[i]; cout< void average(int n,double s[M],double p[M])//按照价值密度的降序排列； { int i,j; double temp1,temp2,temp3,c[M]; for(i=1;i<=n;i++) c[i]=p[i]/s[i]; for(i=1;i for(j=1;j<=n-i;j++) if(c[j] { temp1=p[j];p[j]=p[j+1];p[j+1]=temp1; temp2=s[j];s[j]=s[j+1];s[j+1]=temp2; temp3=c[j];c[j]=c[j+1];c[j+1]=temp3; } }; void bag(int n,double C,double s[M],double p[M],double x[M])//totalp(总价值) { int i; double c1; average(n,s,p); c1=C; while(c1!=0) { for(i=1;i<=n;i++) { if(s[i]<=c1) { x[i]=1; c1=c1-s[i]; } else if(s[i]>c1) { x[i]=c1/s[i]; c1=0; }// totalp=totalp+p[i]*x[i]; }}}; void main() { int i,n; double C=0,totalp=0,s[M],p[M],x[M]; char ch; while(1) { display(n,C,s,p); bag(n,C,s,p,x);//totalp cout<<\结果表示为:\ for(i=1;i<=n;i++) cout<<\第\个物体大小:\s[i]<<\物体价值:\p[i]<<\物体价值密度:\ cout< cout<<\向量表示:\ for(i=1;i<=n;i++) { cout< totalp=totalp+p[i]*x[i];} cout<<\ cout<<\背包的总价值为：\背包所装载总价值 cout<<\按Y或y继续操作，否则按任意键\ cin>>ch; if(ch=='Y'||ch=='y') continue; else break; }} 2、0-1背包装载问题： #include int n,c,bestp;//物品的个数，背包的容量，最大价值 int p[10000],w[10000],x[10000],bestx[10000]; //物品价值，物品重量，x[i]暂存物品的选中 情况,物品选择 void Backtrack(int i,int cp,int cw)//回溯 { if(i>n){ if(cp>bestp){ bestp=cp; for(int j=0;j<=n;j++) bestx[j]=x[j];//选择成功则将物品已选择情况存入bestx[i]} return; } if(cw+w[i]<=c) {//i物品放入背包，搜索左子树 x[i]=1; cw+=w[i]*x[i]; cp+=p[i]*x[i]; Backtrack(i+1,cp,cw);//回溯，物品i不放入背包，递归右子树 cw-=w[i]*x[i]; cp-=p[i]*x[i];}x[i]=0; Backtrack(i+1,cp,cw); 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法设计_课程设计(2)在线全文阅读。
相关推荐：