动态规划解决算法背包问题实验报告含源代码Word文档下载推荐.doc
《动态规划解决算法背包问题实验报告含源代码Word文档下载推荐.doc》由会员分享,可在线阅读,更多相关《动态规划解决算法背包问题实验报告含源代码Word文档下载推荐.doc(7页珍藏版)》请在冰点文库上搜索。
![动态规划解决算法背包问题实验报告含源代码Word文档下载推荐.doc](https://file1.bingdoc.com/fileroot1/2023-4/30/9d7aef54-3f09-4ad4-9a1b-dfb9cc6572e5/9d7aef54-3f09-4ad4-9a1b-dfb9cc6572e51.gif)
VisualC++6.0
二.实验内容
1.设计一个O(n^2)时间的算法,找出由n个数组成的序列的最长单调递增子序列
2.将算法分析题3—1中算法的计算时间减至O(nlogn)
3.给定n种物品和一个背包。
物品i的重量是,其价值为,背包容量为C。
问应该如何选择装入背包的物品,使得装入背包中物品的总价值最大?
三.方案设计
1.动态规划的一个计算两个序列的最长公共子序列的方法如下:
以两个序列X、Y为例子:
设有二维数组f[i,j]表示X的i位和Y的j位之前的最长公共子序列的长度,则有:
f[1][1]=same(1,1);
f[i,j]=max{f[i-1][j-1]+same(i,j),f[i-1,j],f[i,j-1]}
其中,same(a,b)当X的第a位与Y的第b位相同时为“1”,否则为“0”。
此时,二维数组中最大的数便是X和Y的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。
该算法的空间、时间复杂度均为O(n^2),经过优化后,空间复杂度可为O(n)。
核心代码:
voidLCSL(intm,intn,int*x,int*y,intc[][N],intb[][N])
{
c[0][0]=0;
inti,j;
for(i=1;
i<
=m;
i++)
c[i][0]=0;
=n;
c[0][i]=0;
for(i=1;
for(j=1;
j<
j++)
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
elseif(c[i-1][j]>
=c[i][j-1])
c[i][j]=c[i-1][j];
b[i][j]=2;
else
c[i][j]=c[i][j-1];
b[i][j]=3;
}
cout<
<
c[m][m]<
endl;
}
voidLCS(inti,intj,int*x,intb[][N])
if(i==0||j==0)return;
if(b[i][j]==1)
{
LCS(i-1,j-1,x,b);
for(inty=1;
y<
i;
y++)
if(x[y]==x[i])
return;
cout<
x[i]<
"
"
;
}
elseif(b[i][j]==2)
LCS(i-1,j,x,b);
else
LCS(i,j-1,x,b);
voidQuickSort(inta[],intp,intr)
if(p<
r)
intq=Partition(a,p,r);
QuickSort(a,p,q-1);
//对左半段排序
QuickSort(a,q+1,r);
//对右半段排序
通过动态规划求出最长公共子序列,再用任意排序算法,得出最长单调递增序列,我选用的排序方法是快速排序。
2.一个长度为i的候选子序列的最后一个元素至少与一个长度为i-1的候选子序列的最后一个元素一样大,通过只想输入序列中元素的指针来维持候选子序列。
3.0/1背包问题:
现有n种物品,对1<
=i<
=n,第i种物品的重量为正整数Wi,价值为正整数Vi,背包能承受的最大载重量为正整数C,现要求找出这n种物品的一个子集,使得子集中物品的总重量不超过C且总价值尽量大。
动态规划算法描述:
根据问题描述,可以将其转化为如下的约束条件和目标函数:
寻找一个满足约束条件,并使目标函数式达到最大的解向量,使得,而且达到最大。
0-1背包问题具有最优子结构性质。
假设是所给的问题的一个最优解,则是下面问题的一个最优解:
。
如果不是的话,设是这个问题的一个最优解,则,且。
因此,,这说明是所给的0-1背包问题比更优的解,从而与假设矛盾。
按照上面的情况,可以得到递推公式:
设最优值为m(i,j)。
max{m(i+1,j),m(i+1,j-)+}
m(i,j)=
m(i+1,j)
m(n,j)=0
#include<
stdio.h>
intV[200][200];
//前i个物品装入容量为j的背包中获得的最大价值
intmax(inta,intb)
if(a>
=b)
returna;
elsereturnb;
intKnapSack(intn,intw[],intv[],intx[],intC)
inti,j;
for(i=0;
V[i][0]=0;
for(j=0;
=C;
V[0][j]=0;
=n-1;
for(j=0;
if(j<
w[i])
V[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
j=C;
for(i=n-1;
i>
=0;
i--)
{
if(V[i][j]>
V[i-1][j])
{
x[i]=1;
j=j-w[i];
}
x[i]=0;
}
printf("
选中的物品是:
\n"
);
for(i=0;
n;
printf("
%d"
x[i]);
returnV[n-1][C];
voidmain()
ints;
//获得的最大价值
intw[15];
//物品的重量
intv[15];
//物品的价值
intx[15];
//物品的选取状态
intn,i;
intC;
//背包最大容量
n=5;
printf("
请输入背包的最大容量:
scanf("
%d"
&
C);
输入物品数:
n);
请分别输入物品的重量:
scanf("
w[i]);
请分别输入物品的价值:
v[i]);
s=KnapSack(n,w,v,x,C);
最大物品价值为:
%d\n"
s);
四.运行结果
1.
2.
3.
五.心得体会
通过这次实验,对动态规划法求最长公共子序列有更深的理解。
其实无非就是抓住书上的递推公式进行写,动态规划依赖于上一个或者上一行的解,就是在输出子序列的时候有问题。
自己对动态规划、贪心、回溯法、分支限界法的原理不是非常的理解,花了很多时间看了课本上的相关内容。
同时课本所提供的代码也是不能直接翻译过来用,当懂得算法的基本原理后,会发现数组下标会出错,所以在参考课本所提供的代码的同时,必须结合算法的实际情况对代码中的相关变量进行修改,这样才能充分利用课本所提供的代码完成本次实验。
通过本次试验,自己基本上掌握上述算法原理,达到实验的目的。