logo资料库

0-1背包问题（动态规划）报告.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.12M 资料格式：doc 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    实验八：0-1背包问题（动态规划）报告
    1．问题描述
    给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品
    2．实验目的
    3．实验原理
    4．实验设计
    5．实验结果与分析
    6．结论
    7．程序源码
    实验八：0-1 背包问题（动态规划）报告 2017061111 李静娴 1．问题描述 给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问:应如何 选择装入背包的物品，使得装入背包中物品的总价值最大? 2．实验目的 （1）熟悉动态规划算法，并学以致用 （2）熟练掌握 0-1 背包问题算法 3．实验原理 设所给 0-1 背包问题的子问题的最优值为 m(i，j)，即 m(i，j)是背包容量为 j，可选择物 品为 i，i+1，…，n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性质，可以建 立计算 m(i，j)的递归式: 时间为 算法时间复杂度分析： q[i+1]需要 O(|p[i+1]|)计算时间。合并 p[i+1]和 q[i+1]并清除受控跳跃点也需要 O(|p[i+1]|)计 算时间。从跳跃点集 p[i]的定义可以看出，p[i]中的跳跃点相应于 xi,…,xn 的 0/1 赋值。因此， 算法的主要计算量在于计算跳跃点集 p[i](1≤i≤n)。由于 q[i+1]=p[i+1]⊕(wi,vi)，故计算 p[i]中跳跃点个数不超过 2^(n-i+1)。由此可见，算法计算跳跃点集 p[i](1≤i≤n)所花费的计算 |p[i]|≤c+1，其中，1≤i≤n。在这种情况下，改进后算法的计算时间复杂性为 O(min{nc,2^n}。 从而，改进后算法的计算时间复杂性为 O(2^n)。当所给物品的重量 wi 是整数时， 4．实验设计 1]|)= ( O  i  2 n i 2 )   i  2 O (  O n (2 ) n | [ p i  n （1） 输入数据格式：输入背包的容量和物品的个数，要求都为整型的数 生成方式：在输入数据规模之后，程序中先生成基于当前时间的随机数种子，然后通过 for 循环语句，每次用随机函数生成一个范围在 1-30 的随机数并将其放入物品重量数组 w[]中。 同样的方式生成范围在 1-100 的随机数并将其放入物品重量数组 v[]中。 数据规模：用户手动输入数据规模。 （2）
    该程序先是基于当前系统时间生成随机数种子，再根据输入的数据规模创建两个相应大 小的整型数组，然后通过 for 循环语句和随机函数 rand()循环生成数据规模个数的元素并存 入创建的数组中。然后调用 knapsack(n,w,v,c,p,head,x)函数，并在调用函数的前后使用 clock() 函数记入时间，用于计算算法的运行时间并输出。同时，在 knapsack(n,w,v,c,p,head,x)函数里 输出装入的物品序列。 （3） 程序运行的结果有五个，先是打印物品的重量列表 w，接着打印物品的价值列表 v，然 后最优值，即在背包容量允许下能装入的物品最大价值，再输出最优解，即选择的物品方案， 最后输出算法运行时间。 5．实验结果与分析 由此可见程序运行结果无误。 接下来再加几个测试用例，以便验证算法时间按复杂度。
    测试结果： 背包容量 c 物品个数 n 5 10 20 100 100 100 nc 2^n min{nc,2^n} 算法运行时间（单位：秒） 500 1000 2000 32 1024 1048576 32 1000 2000 0.33 0.336 0.343 在一定的误差允许范围内，可见算法运行时间与 min{nc,2^n}成线性关系。 6．结论 我用随机数方法给物品重量数组和物品价值数组赋值，这样节省了人力。为了使程序更 具有交互性，我选择动态生成数组。这里 p[][]我选择了 vector 的方式,w[]和 v[]我选择堆 方式。程序中 p[][0]存储已经装入物品的总重量,p[][1]存储已经装入物品的总价值，这里， 在定义声明时我需要确定 vector p[][]的维度，我经过推理后得到，n 个物品 p 最多有 2^n 项，因此，当我限制 n 最大为 20 时，p 的维数就可以写成这样：p[1048576][2],最后，我 经过 excel 工具处理分析数据得出结论，算法运行时间与 min{nc,2^n}成线性关系。
    7．程序源码 #include #include #include #include #include using namespace std; void knapsack(int n,double w[],double v[],int c,vector> p,int head[],int x[]){ head[n+1]=0; p[0][0]=0;//p[][0]存储物品重量 p[0][1]=0;//p[][1]存储物品价值，物品 n 的跳跃点(0,0) int left=0,right=0,next=1;//left 指向 p[i+1]的第一个跳跃点,right 指向最后一个 //next 即下一个跳跃点要存放的位置 head[n]=1;//用来指向第 n 个物品第一个跳跃点的位置 for(int i=n;i>=1;i--){ int k=left;//k 指向 p[]中跳跃点，移动 k 来判断 p[]与 p[]+(wv)中的受控点 for(int j=left;j<=right;j++){ if(p[j][0]+w[i]>c) break;//剩余的空间不能再装入 i,退出 for 循环 double y=p[j][0]+w[i],m=p[j][1]+v[i];//计算 p[]+(wv) //若 p[k][0]较小则(p[k][0],p[k][1])一定不是受控点，将其作为 p[i]的跳跃点存储 while(k<=right&&p[k][0]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; } //x[]数组存储对应物品 0-1 向量，0 不装入背包，1 装入背包 //初始化 j,m 为最后一个跳跃点对应的第 0 列及第一列 double j=p[head[0]-1][0]; double m=p[head[0]-1][1]; for(int i=1;i<=n;i++){ x[i]=0;//初始化数组 for(int k=head[i+1];k<=head[i]-1;k++){//初始 k 指向 p[2]的第一个跳跃点（0，0) //判断物品 i 是否装入 if(p[k][0]+w[i]==j&&p[k][1]+v[i]==m){ x[i]=1;//物品 i 被装入，则 x[i]置 1 j=p[k][0];//j 和 m 置为满足 if 条件的跳跃点对应的值 m=p[k][1]; break;//再接着判断下一个物品 } } } cout<<"最优值是："<>c; cout<<"自定义物品个数(<=20)："<
    cin>>n; double *w=new double[n+1]; double *v=new double[n+1]; int *head=new int[n+2]; int *x=new int[n+1]; vector> p(1048576);//经推理得，p[][]的第一维最多有 2^n，n 为物品个 数 for(int i=0;i
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料