数据结构——背包问题
(2007-03-15 10:36:01)
转载
[题目]第2.1背包问题
一．实验内容：
设有一个背包可以放入的物品的重量为S，现有N件物品,重量分别为W1,W2,W3……Wn。问能否从这n件物品中选择若干件放入此包中，使得放入的物品的重量之和正好为S。
二．实验的目的：
深入了解栈和队列的特性，以便在实际问题背景下灵活应用，同时还将巩固对这两中结构的构造方法的掌握，接触较复杂问题的递归算法的设计。
三．实验设计思想：
（1）递归策略
在该问题中物品质量W[n]和包所能承受的最大重量maxweight都是又用户自己任意定义的，在递归实现的过程中用到一个栈来实现。第i件物品的选择有两种可能：
i. 物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后。继续递归去考虑其余物品的选择；
ii. 物品i不被选择，这种可能性仅当不包含物品i不满足条件的情况。现以第一个物品为例，当物品1不被选择，则问题转变为相对于其他物品（2，3，……，n），背包重量仍然为maxweight；若物品1被选择，问题就变为关于最大背包重量为maxweight-w[1]的问题，现设r{maxweight, maxweight-w[1]}为剩余重量的背包问题。
此背包的递归定义为：
True s=0 此候背包问题一定有解
False s<0 总重量不能为负数
False s>0且n<1 物品件数不能为负数
F(s,n-1) s>0且n≧1 所选物品中不包括w[n]时
F(s-w[n],n-1) s>0且n≧1 所选物品中包括w[n]时
F(s,n)
（2）非递归策略
非递归策略思想的实现与递归策略类似，只是直接用定义一个栈来实现，同样的物品质量W[n]和包所能承受的最大重量maxweight都是又用户自己任意定义的，第i件物品的选择有两种可能：
iii. 物品i的重量不会超过方案中所剩重量时进栈保存。
iv. 物品i不进栈，这种可能性仅当不包含物品i不满足条件的情况。
现以第一个物品为例，当物品1不满足条件时，则问题转变为相对于其他物品（2，3，……，n），背包重量仍然为maxweight；若物品1被选择，问题就变为关于最大背包重量为maxweight-w[1]的问题，现设r{maxweight, maxweight-w[1]}为剩余重量的背包问题。
当i从1到了n，但是并没有找到重量之和为maxweight时，元素则要求出栈，继续下一个，直到所以的都经过排列后，如果还是没有才是失败。
程序流程图：
1) 定义stack[NUMBER]，用于存放暂时满足要求的物品。
2) 定义主函数。
3) 定义被调用函数，用于实现函数，并将满足总容量要求的打印，最后输入任意的maxweight和W[n]就可以输出解。
四．程序具有的结构模块：
主函数main() 调用子函数f()
五．程序使用方法：
首先要对需要处理的货物数量，货物的容量和包的最大容量进行定义，本题以6件物品为例。程序运行时提示“Please input maxweight :”，这时操作者输入包能容下的最大容量，程序提示“NUMBER :”，再输入总数量，程序再次提示“Please input every object's weight :”
输入每件物品的容量，用空格或回车间隔，待输入数目达到定义的数目6并按回车键。程序给出“SUCCESS !”或者“FAIL!”，如果成功将输出成功的组合，结束。
六．程序测试结果：
（1）输入：Please input maxweight :
16
NUMBER :
6
Please input every object's weight :
1 2 3 4 5 1
Main()
f()查找函数
程序结构图
输出：SUCCESS !
The weight is :
weigh[6]= 1 weigh[5]= 5 weigh[4]= 4
weigh[3]= 3 weigh[2]= 2 weigh[1]= 1
Press any key to continue
（2）输入：Please input maxweight :
16
NUMBER :
6
Please input every object's weight :
输出：7 8 10 12 14 15 13
FAIL!
Press any key to continue
七．程序源代码：
（1）递归算法
#include "stdio.h"
#define NUMBER 20 /*定义物品个数*/
int w[NUMBER]; /*存放物品质量的数组*/
int s;
int n;
void main()
{
int f( int, int); /*被调用函数的声明*/
int i;
printf("Please input maxweight :\n");
scanf("%d",&s); /*输入包所能承受的最大重量*/
printf(" NUMBER :\n");
scanf("%d", &n); /*输入物品的个数*/
printf( " Please input every object's weight :\n" );
for (i=1; i<=n; i++ )
scanf("%d",&w[i]); /*分别输入n件物品的重量*/
if (f(s,n ) == 1 ) /*调用背包处理函数并且成功*/
printf("SUCCESS !\n");
else printf("fail\n");/*失败*/
}
int f(int s,int n) /*背包问题处理函数*/
{
if(s==0) return 1; /*当时包问题一定有解*/
if( s<0||s>0&&n<1) return 0; /*总重量或者数量为负肯定都无解*/ if(f(s-w[n],n-1)== 1)
{
printf("%d,",w[n]); return 1;
}
return f(s,n-1);
}
（2）非递归算法
#include "stdio.h"
#define NUMBER 20 /*定义物品个数*/
int stack[NUMBER]; /*定义一个栈，用于存放元素*/
int top; /*用于记录栈中的元素个数*/
void main()
{
int f( int, int, int[]);/*被调用函数的声明*/
int weight[NUMBER]; /*存放物品重量的数组*/
int n, i;
int maxweight; /*包所能承受的最大重量*/
printf("Please input maxweight :\n");
scanf("%d",&maxweight); /*输入包所能承受的最大重量*/
printf(" NUMBER :\n");
scanf("%d", &n); /*输入物品的个数*/
printf( " Please input every object's weight :\n" );
for (i=1; i<=n; i++ )
scanf("%d",&weight[i]); /*分别输入n件物品的重量*/
if (f(n, maxweight, weight ) == 1 ) /*调用背包处理函数并且成功*/ { printf("SUCCESS !\n");
printf("The weight is :\n");
for ( ;top>0;top-- )
printf("weigh[%d]=%4d ", stack[top],weight[stack[top]]); /*栈中元素出栈，并打印包的容量*/
printf("\n");
}
else /*不成功的处理*/
printf("FAIL!\n");
}
int f( int n, int maxweight, int weight[] ) /*背包问题处理函数*/
{
int i=1;
top=0;
if(maxweight==0) return 1;
while ((maxweight>0)&&(i<=n))
{
if ((maxweight-weight[i]==0) || ((maxweight-weight[i] >0 )&& (i { stack[ ++top ]=i; /*将第i个元进栈*/ maxweight = maxweight-weight[i]; /*总重量的变化*/ } if ( maxweight==0) /*能够装入包中*/ { return 1 ; /*终止试探并返回成功*/ } else if (( i==n )&& (top>0)) /*继续试探*/ { i=stack[top]; top=top-1; maxweight=maxweight+weight[i]; } i++; } return 0 ; /*试探失败*/ } 八．设计心得： 动态规划方法对解决问题很有帮助，在这个背包问题中就是一个体现。递归是栈的主要应用之一，本题看起来是一个比较麻烦复杂的题目，当用到递归的思想时，就可以把它比较轻松的解决。同时我们可以把递归转化为非递归的算法。 通过这道题，使我们巩固了平时所学的知识，对数据结构中递归与非递归的思想有了进一步的理解和认识，更重要的是通过这个题目使我们更多的了解到数据结构在实际问题中的广泛应用。 使用穷举法解决0—1背包问题 问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。 设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中，限制重量为tw.考虑一个n元组（x0，x1，…，xn-1），其中xi=0 表示第i个物品没有选取，而xi=1则表示第i个物品被选取。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n元组，就可以得到问题的解。 显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0～2n-1.因此，如果把0～2n-1分别转化为相应的二进制数，则可以得到我们所需要的2n 个n元组。 下面是我据此思路编的一个小程序。 程序在VC6.0，win xp下编译运行成功。 程序测试结果，截图如下： 背包问题的递归算法 #include //物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了#define N 100 int n ; //物品总种数 double limitW ; //限制的总重量 double totV ; //全部物品的总价值 double maxv ; //解的总价值 int option[N]; //解的选择 int cop[N]; //当前解的选择 struct { //物品结构 double weight ; double value ; }a[N]; //参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值void find(int i,doubletw,double tv) { int k ; //物品i包含在当前方案的可能性 if(tw+a.weight<=limitW) { cop=1 ; if(i { find(i+1,tw+a.weight,tv); } else { for(k=0;k option[k]=cop[k]; maxv=tv ; } } cop=0 ; //物品i不包含在当前方案的可能性 if(tv-a.value>maxv) { 全国密码技术竞赛模拟练习题一?单项选择题(共40题，每题1分) 1 ?首次提出公钥密码体制的概念的着作是()。 A.《破译者》 B.《密码学新方向》 C.《保密系统的通信理论》 D.《学问的发展》n 2?利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是Ell(l,6),生成元G=(2, 7),接收方A的私钥钥nA二7,公钥PA二(7, 2),发送方B欲发送消息Pm二(10, 9),选择随机数23,求密文Cm二()□ 「A. { (2,3), (5, 2) } 「B. { (3,2), (6, 2) } r C. { (& 3), (10, 2) } 「D. { (6,5), (2, 10) } 3.线性密码分析方法本质上是一种()的攻击方法 A.唯密文攻击 B.已知明文攻击 C.选择明文攻击 D.选择密文攻击戸 4.（）算法抵抗频率分析攻击能力最强，而对已知明文攻击最弱。 厂A.仿射密码 C B.维吉利亚密码 「C.轮转密码 厂D.希尔密码 5.从事国家秘密载体制作、复制、维修、销毁，涉密信息系统集成，或者武器装备科研生产等涉及国家秘密业务的企业事业单位，应当经过保密审查，具体办法由____ 规定。（） 厂A.法院 厂B.检察院 「C.密码管理机构 r D.国务院 6.下面的说法中错误的是（）。 「A.传统的密钥系统的加密密钥和解密密钥相同r B.公开密钥系统的加密密钥和解密密钥不相同 C C.报文摘要适合数字签名但不适合数据加密 C D.数字签名系统一定具有数据加密功能— 7.下列（）算法不具有雪崩效应。 加密 B.序列密码的生成 f C.哈希函数 r加密 使用不方便的最大问题是（）。 「A.产生密钥需要强大的计算能力 C B.算法中需要大数 r C.算法中需要素数 「D.被攻击过许多次 9.可证明安全属于下列（）范畴中 厂A.加密安全性 C B.解密安全性 「C.计算安全性 厂D.实际安全性 年，（）发表题为《保密系统的通信理论》的文章，为密码系统建立了理论基础, 从此密码学成了一门科学。 《算法分析与设计》实验指导. 实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这 样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。 算法分析与设计实验报告第五次附加实验 附录： 完整代码（回溯法） //0-1背包问题回溯法求解 #include Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组| Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template 潍坊信息学竞赛注意事项 一、复赛内容与要求： 在初赛的内容上增加以下内容： A．数据结构： 1．指针类型 2．多维数组 3．单链表及循环链表 4．二叉树 5．文件操作（从文本文件中读入数据，并输出到文本文件中） B．程序设计 1．算法的实现能力 2．程序调试基本能力 3．设计测试数据的基本能力 4．程序的时间复杂度和空间复杂度的估计 C．算法处理 1．离散数学知识的应用（如排列组合、简单图论、数理逻辑） 2．分治思想 3．模拟法 4．贪心法 5．简单搜索算法（深度优先广度优先）搜索中的剪枝 6．动态规划的思想及基本算法 二：注意事项 1. 务必看清题目，严格按照所要求的格式输入、输出。 2. 在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。特别注意最大值与最小值（极值）。 3. 测试有严格的时间限制，请尽可能优化算法。 4. 命名规则：各题都规定了该题的英文名称。要求提交程序的文件名一律采用小写。程序文件和数据文件的主文件名都是该题的英文名字。程序文件扩展名采用语言环境的默认扩展名。数据文件都是文本文件，输入数据文件和输出数据文件的扩展名分别是.in和.out。 5. 程序应从输入文件中读取数据，然后把结果严格地按照规定的输出格式输出到输出文件中。 6. 考试题目在考试微机的D:/盘下“prlblem”文件夹中，考试结束请将程序放到以“你的考号+姓名”（中间无空格）命名的文件夹中，并将此文件夹放到D:/盘下“test”文件夹中,考试结束后此文件夹要处于打开状态方可离开考场。 选手请认真核对提交的源程序的文件名，写错的文件名的题得0分。 如何骗分： 对于一个约定无解输出-1的题目，骗分者只写一行代码就可以把无解的部分分数拿到，有时把示例输出也可能拿到10分。这只是万不得已的情况。最好是依靠实力拿分。 空间复杂度不能超过内存限制，一般情况下数组不宜开的过大。如果开一个10数组将会出现内存不足的情况，这时就要设计一个优秀的算法来优化空间性能只找出实际有用的信息。 华东师范大学计算机科学技术系上机实践报告 课程名称：算法设计与分析年级：05上机实践成绩： 指导教师：柳银萍姓名：张翡翡 上机实践名称：贪心算法学号：10052130119上机实践日期：2007-4-10 上机实践编号：NO.2组号：上机实践时间：10:00-11:30 一、目的 了解熟悉掌握贪心算法实质并学会灵活运用，从而解决生活中一些实际问题。 二、内容与设计思想 1.超市的自动柜员机(POS)要找给顾客各种数值的现金，表面上看，这是一个很简单的任务，但交给机器办就不简单了。你作为一个计算机专家，要求写一个程序来对付这个“简单”的问题。 你的自动柜员机有以下的币种：100元，50元，20元，10元，5元，2元，1元。你可以假设每种钱币的数量是无限的。现在有一笔交易，需要找个客户m元，请你设计一个算法，使得找给顾客的钱币张数最少。 要求： 输入：第一行仅有一个整数n(0 课程设计报告 课程名称数据结构课程设计 课题名称背包问题 专业信息与计算科学 班级1001班 学号22 姓名王锐 指导教师刘洞波张晓清郭芳 2012年6月9日 课程设计任务书 课程名称数据结构课程设计课题背包问题 专业班级信科1001班 学生姓名王锐 学号22 指导老师刘洞波张晓清郭芳 审批刘洞波张晓清郭芳 任务书下达日期：2012年6月9日 任务完成日期：2012年6月16日 一、设计内容与设计要求 1．设计内容： 1）问题描述 假设有一个能装入总体积为T的背包和n件体积分别为W1，W2，···，Wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使W1+W2+···+Wn=T，要求找出所有满足 上述条件的解。例如：当T=10，共6件物品，物品的体积为{1，2，3，4，5，8}，那么 可找到下列4组解：（1，2，3，4）、（1，4，5）、（2，3，5）、（2、8）。 2）实现提示 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品， 若该件物品“太大”不能装入，则丢弃而继续选取下一件，直至背包装满为止。但如果在 剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合 适”，应将它取出“丢弃一边”，继续再从“它之后”的物品中选取，如此重复，直至求得 满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”，因此要用到栈。 2．设计要求： 课程设计报告规范 1)需求分析 a.程序的功能。 b.输入输出的要求。 2)概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。 b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构， 它们之间有什么关系等。 3)详细设计 a.采用C语言定义相关的数据类型。 b.写出各模块的类C码算法。 c.画出各函数的调用关系图、主要函数的流程图。 《数据结构》课程设计 课程名称：数据结构 完成时间：3周学分： 1 一、课程设计的目的与任务 课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。《数据结构》是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，为今后从事计算机开发与应用打下基础。新世纪需要具有丰富科学知识、独立解决实际问题、有创造能力的新型人才，这也是该课程设计的最终目的。 二、本课程设计的基本理论 《数据结构》课程设计中牵涉到本课程中的六个主要章节的基本理论，包括基本数据结构（线性结构（线性表、栈、队列）、图、树）的特点、存储方式、运算原理和方法、典型应用和两种重要操作查找、排序的基本原理与方法。 三、课程设计的基本要求 基本要求：通过这次设计，要求在分析计算机处理对象的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面加深对课程基本内容的理解。要求每个学生在规定的时间内完成一组中2个应用问题，并根据所选问题分析设计思路、选择数据结构描述、确立算法过程、用一种计算机语言（例如C++、Java）（最好是C++）编写出详细的实现程序，然后通过上机反复调试与修改，直到获得满意的结果为止。对于要解决的同一问题，由于所采用的数据结构可能不同、所选择的算法可能不同、编写的程序也不仅相同，但只要结果正确且有效（具有较好的时间复杂度和空间复杂度）即可，即不要求编写的算法和程序完全一致，但力求编写的算法和程序更优秀、综合指标更好。 注意：杜绝抄袭，一经查证一律0分 四、课程设计的内容 1. 文本处理 【问题描述】打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘 【基本要求】 (1)完成上述功能，数据结构不限 (2)尽量高效 东莞理工学院C语言课程设计 课程程序设计基础 题目 院系名称计算机学院 班级 学生姓名学号 组员 指导教师 时间 1 问题要求及任务描述 1.1 题目要求 假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求 找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5， 2}时，可找到下列4组解： （1，4，3，2） （1，4，5） （8，2） （3，5，2）。 1.2 主要任务 在给定物品数量，物品各自体积和背包体积的前提下，找出物体组合后的总体积与背包体积相等的物体组合 2 解决问题的主要思路和方法 2.1 关键问题 如何选择第i件物品： （1）考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续去考虑其余物品的选择。 （2）考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 2.2 拟采用解决问题的方法 可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品"太大"不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明"刚刚"装入背包的那件物品"不合适"，应将它取出"弃之一边"，继续再从"它之后"的物品中选取，如此重复，直至求得满足条件的解，或者无解。 2.3 主要算法和处理流程图 1．输入物品总个数 2．依次输入各物品的体积 3．输入背包总体积 4．将物品排成一列，按顺序选取物品装入背包中，当物品太大不能装入时则弃之继续选取下一件，直到背包装满为止， 5．出现在剩余的物品中找不到合适的物品填满背包的情况是说明刚刚装入背包的那件物品不适合，将它取出后继续选取后面的物品。6．重复步骤4和5直至求出满足条件的解或者无解。 动态规划 1.最佳队形（bestqueue; 时限:1s; 128MB） 【题目描述】 要参加复赛了，大家都在体育馆门口集合完毕，由于这次参赛的人数较多，上车前需要排一下队，所有人自愿排成两队（分别定义为A和B队列，人数大于1且两队人数随意），Ms. Zhou给每位同学一张纸，每人默默写下一个字母代表自己，比如：郑逸宁写Z，吴天舒写W等等。 A队： 字母：c m c B队： 字母：s n m n 最佳队形为： 1、每个人前后可以有任意个空位，也可以没有空位； 2、两队在添加空位后长度必须一样，上图可以有多种方案使得A、B两队长度一致， 例如： 3、根据每个人所写的字母，我们定义A队与B队的距离为相应位置上的字母的距离总 和； 4、两队相应位置的距离定义为： （1）两个非空位的距离定义为它们的所写字母ASCII码的差的绝对值； （2）空位与其他任意非空位之间的距离为已知的定值K； （3）空位与空位的距离为0。 5、最佳队形为：在A、B的所有可能队形中，必定存在两个等长的队A’、B’，使得A’ 与B’之间的距离达到最小，这个队形就是最佳队形。 请你写一个程序，求出最佳队形时，A队与B队的距离。 【输入数据】 输入文件第一行为队列A每个人所写字母组成的字符串A； 第二行为队列B每个人所写字母组成的字符串B。（约定：A、B均由小写字母组成且长度均不超过2000）。 第三行为一个整数K（1≤K≤100），表示空位与非空位的距离。 【输出数据】 输出文件仅一行包含一个整数，表示所求得最佳队形A、B之间的距离。 【样例】 bestqueue.in bestqueue.in cmc 10 snmn 2 2. 数学作业（homework; 时限:1s; 128MB） 【问题描述】 数学竞赛刚刚结束，据说题目很难，不过信息学里面的数学题也不容易哦，题目描述很简单：求：方程x1+2x2+…+nx n=m的所有非负整数解（x1,x2,…,x n）的个数。例如，方程：x1+2x2+3x3+4x4+5x5=5有7组解：（5,0,0,0,0）、（3,1,0 ,0,0）、…、（0,0,0,0,1）。 运用你的数学思维加上强大的信息学能力，试试解决它吧！ 【输入数据】 2个整数n，m 【输出数据】 方程非负整数解的个数ans，如果解超过10^9，只需输出ans mod 10^9。 数据结构——背包问题 (2007-03-15 10:36:01) 转载 [题目]第2.1背包问题 一．实验内容： 设有一个背包可以放入的物品的重量为S，现有N件物品,重量分别为W1,W2,W3……Wn。问能否从这n件物品中选择若干件放入此包中，使得放入的物品的重量之和正好为S。 二．实验的目的： 深入了解栈和队列的特性，以便在实际问题背景下灵活应用，同时还将巩固对这两中结构的构造方法的掌握，接触较复杂问题的递归算法的设计。 三．实验设计思想： （1）递归策略 在该问题中物品质量W[n]和包所能承受的最大重量maxweight都是又用户自己任意定义的，在递归实现的过程中用到一个栈来实现。第i件物品的选择有两种可能： i. 物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后。继续递归去考虑其余物品的选择； ii. 物品i不被选择，这种可能性仅当不包含物品i不满足条件的情况。现以第一个物品为例，当物品1不被选择，则问题转变为相对于其他物品（2，3，……，n），背包重量仍然为maxweight；若物品1被选择，问题就变为关于最大背包重量为maxweight-w[1]的问题，现设r{maxweight, maxweight-w[1]}为剩余重量的背包问题。 此背包的递归定义为： True s=0 此候背包问题一定有解 False s<0 总重量不能为负数 False s>0且n<1 物品件数不能为负数 F(s,n-1) s>0且n≧1 所选物品中不包括w[n]时 F(s-w[n],n-1) s>0且n≧1 所选物品中包括w[n]时 F(s,n) （2）非递归策略 非递归策略思想的实现与递归策略类似，只是直接用定义一个栈来实现，同样的物品质量W[n]和包所能承受的最大重量maxweight都是又用户自己任意定义的，第i件物品的选择有两种可能： iii. 物品i的重量不会超过方案中所剩重量时进栈保存。 iv. 物品i不进栈，这种可能性仅当不包含物品i不满足条件的情况。 现以第一个物品为例，当物品1不满足条件时，则问题转变为相对于其他物品（2，3，……，n），背包重量仍然为maxweight；若物品1被选择，问题就变为关于最大背包重量为maxweight-w[1]的问题，现设r{maxweight, maxweight-w[1]}为剩余重量的背包问题。 八皇后问题 1.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行……第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。 2.基本要求 编写求解并输出此问题的一个合法布局的程序。 3、实现提示： 在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。 4 程序代码 #include { int Line,Column; //棋盘初始化，空格为*，放置皇后的地方为@ for(Line=0;Line<8;Line++) { a[Line]=0; //列标记初始化，表示无列冲突 for(Column=0;Column<8;Column++) Queen[Line][Column]='*'; } //主、从对角线标记初始化，表示没有冲突 for(Line=0;Line<15;Line++) b[Line]=c[Line]=0; qu(0); return 0; } void qu(int i) { int Column; for(Column=0;Column<8;Column++) { if(a[Column]==0&&b[i-Column+7]==0&&c[i+Column]==0) //如果无冲突 { Queen[i][Column]='Q'; //放皇后 a[Column]=1;//标记，下一次该列上不能放皇后 b[i-Column+7]=1;//标记，下一次该主对角线上不能放皇后 c[i+Column]=1;//标记，下一次该从对角线上不能放皇后 if(i<7) qu(i+1); //如果行还没有遍历完，进入下一行 else//否则输出 《算法设计与分析》课程综合设计性实验要求 一、实验对象：必修或选修《算法设计与分析》课程的同学。 二、截至时间：2013-12-08之前，由学委统一收了并对文件名命名整理，后打包用邮件来交。 三、实验内容： 0-1背包问题是一例典型的组合优化的NP完全问题。问题可以描述为：给定一组共n个物品，每种物品都有自己的重量wi, i=1~n和价值vi, i=1~n，在限定的总重量（背包的容量C）内，如何选择才能使得选择物品的总价值之和最高。选择最优的物品子集放置于给定背包中，最优子集对应n元解向量(x1,…xn), xi∈{0或1}，因此命名为0-1背包问题。 0-1背包问题是许多问题的原型，但它又是一个NP完全问题。此实验主要研究和实现n(0<=n<=200)和C(C<=2000, C为整数)都较大的情形，随机产生n个物品的重量向量wi(1<=wi<=100, wi为整数)和价值向量vi (1<=vi<=100, vi为整数)。 0-1背包问题可以用许多方法来求解，有些算法可以得到问题的精确最优解，有些仅能获得一个近似最优解。本综合设计性实验要求用3种以上的方法求解0-1背包问题，获得精确最优解或近似最优解皆可，并对所采用的多种算法从运行时间、寻找是否为最优解、能够求解的问题规模等方面进行对比和分析。本课程讲述的所有算法思想都可以用来求解此问题，甚至本课程未涉及的许多算法也非常适合于求解此问题，学生可以先尝试先用本课程已介绍的算法来实现和分析，学有余力或兴趣驱动下可以寻找一些智能算法的资料来试一试。涉及的方法可以有：蛮力求解、递归求解、动态规划求解、贪心求解、回溯法求解、广度优先的分支限界法求解，优先队列的启发式分支限界法、遗传算法、模拟退火算法、蚁群算法、粒子群算法等。 为方便这种大规模输入数据的调试，采用文件输入，标准输出（文件输出当然也可）的形式。数据输入的格式如下：每组测试数据包含n+1行，第1行为C和n，表示背包容量为C且有n个物品，接下来n行是这n 个物品的重量wi和价值vi。背包容量和物品重量都为整数。n, C , wi, vi范围如上所述。 输出n+1行。第1行为所选物品的最大价值之和，接下来n行为装入背包的物品所对应的n元最优解向量(x1,…xn), xi∈{0或1}，但每行以"i xi"形式输出。 提供一个参考的测试数据（“0-1背包问题测试数据(提供参考).xls”）给大家，此数据仅用参考，你也可自拟测试数据，对有些复杂度较高的算法可能算不到参考数据中的最大规模的数据（或算的时间过长），但能算到多大要测试一下你的算法。 四、实验形式： 不超过3人（小组成员人数≤3人）形成一组，自由组合，若凑不够人数就2人或单人也可。一组只交一份报告，报告封面上需将小组所有成员的姓名和学号填入，在报告中开始部分说明小组成员的分工。先透彻理解实验内容，然后思考算法及实现框架，并编程调试测试通过，最后执笔完成《综合设计性实验的实验报告》。 综合设计性实验报告以“电子版”的形式上交，以班级为单位收集好，由每个班学习委员统一收齐电子版 算法分析与设计实验报告第三次实验 测试结果 输入及背包容量较小的结果（数据手动收入）： 输入及背包容量中等大小的结果（数据由随机函数产生）： 输入及背包容量较大的结果（数据由随机函数产生）： 附录： 完整代码 //0-1背包问题，动态规划算法 #include int main() { int c,n; cout<<"请输入背包的容量："; cin>>c; cout<<"请输入物品的个数："; cin>>n; int *v=new int[n+1]; int *w=new int[n+1]; //下标从1开始 int x[N+1]; int **m; int i; m=new int *[n+1]; for(i=0;i 算法分析与设计任务书 1 课程设计的目的 《算法分析与设计》是信息与计算科学专业集中实践性环节之一，是学习完《算法分析与设计》课程后进行的一次全面的综合练习。其目的是：（1）要达到理论与实际应用相结合，使学生能够学会常用的几种算法思想以及对算法进行分析，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。 （2）在实践中认识为什么要学习算法分析与设计，掌握算法的设计思想与程序设计语言之间的关系，是前面所学知识的综合和回顾。 2 课程设计的基本要求 （1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； （4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风； （5）设计的题目要求达到一定工作量，并具有一定的深度和难度； （6）编写出课程设计说明书。 3 课程设计内容及安排 （1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ （2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操 作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图； （3）详细设计：定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作进行进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架； （4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚； （5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； （6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析； （7）撰写课程设计报告。 4 课程设计报告的内容 设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整，内容及要求详见“课程设计报告规范”，其中“3. 课程设计报告内容”中一般应包括以下内容： 4.1 需求分析 以无歧义陈述说明程序设计的任务，强调的是程序要做什么？并明确规定： (1) 输入的形式和输入值的范围； (2) 输出的形式； (3) 程序所能达到的功能； (4) 测试数据：包括正确的输入和输出结果，含有错误的输入和输出结果。 南通大学 算法设计与分析 实验报告 姓名：鹿瑶 班级：软件工程122 学号：1213042037 日期：2014 . 12 . 16 目录 Question-2编程实现循环赛日程表（分治法） (3) Question-3编程实现最长公共子序列（动态规划） (3) Question-4 The Triangle（动态规划） (4) Question-5超级台阶（动态规划） (5) Question-6最大和（动态规划） (6) Question-7 剑客决斗（动态规划） (7) Question-8最长上升子序列问题（动态规划） (8) Question-9独木舟上的旅行（贪婪法） (9) Question-10背包问题（贪心算法） (10) Question-11田忌赛马（动规中的贪心算法） (10) Question-12硬币问题（贪心算法） (11) 附：源代码 (12) Question-2编程实现循环赛日程表（分治法） 描述 设有n=2 k 个运动员要进行网球循环赛，先要设计一个满足一下要求的比赛日常表： （1）每个选手必须与其他n-1 个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1 天 算法设计 将n*n个格子，也就是n阶方阵从中间十字划分，一次划分分成四块，令其右上角和左下角的数据完全相同，右下角和左上角的数据完全相同；每次划分都得到了若干个n/2阶的方阵，然后对这些方阵进行操作，继续令其右上角和左下角的数据完全相同，右下角和左上角的数据完全相同，如此循环下去，直至n<2时结束递归。 运行结果 Question-3编程实现最长公共子序列（动态规划） 描述 如题，需要你做的就是写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是 所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0 数据结构课程设计报告 设计题目：背包问题 院系：经济管理学院 专业班级：电子商务2011-2 学生姓名：刘燕、李文慧、吴坤 指导教师：周长红 2013年7月5日 目录 1.设计内容 (1) 1.1问题描述 (1) 1.2设计要求 (1) 1.3开发环境 (1) 1.4研究思路 (1) 2.设计步骤 (3) 2.1需求分析 (3) 2.2概要设计 (4) 2.3详细设计 (7) 2.4调试分析 (18) 2.5测试结果 (18) 3.设计成果展示 (25) 3.1用户手册 (25) 3.2程序运行部分截图 (25) 4.总结与心得体会 (28) 附录 (32) 1.设计内容 1.1问题描述 有不同价值、不同重量的物品n件，取出若干件放在空间为C的背包里，每件物品的重量为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。注意：在本题中，所有的重量值均为整数，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。 1.2设计要求 （1）输入n件物品，并随机产生n个物品的各自的重量以及各自的价值； （2）输入背包的总承重； （3）输出总的可能方案数及其具体的放置方法。 1.3开发环境 C-free 5.0 1.4研究思路 本问题给定n种物品和一个背包。物品i的重量是wi，其价值为pi，背包容量为c。问应如何选择装入背包中的物品，使 得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题也称为0-1背包问题。 根据分析，我们选择了分支限界法以及回溯法的思想解决该背包问题。分支限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解，以广度优先或以最小耗费优先的方式搜索解空间树。 数据结构课程设计参考范例与实验备选题目。 同学们可以从中任意选择出 2道题目当作这次设计的内容。建议尽量选择不同的题目。在实验报告中填写的为实际已经实现部分的内容。 数据结构课程设计参考范例 1 ．实验题目 编制一个演示单链表插入、删除、查找等操作的程序 2 ．需求分析 本演示程序用 Turbo C 编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。 ① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数 ② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 ③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作 ④ 测试数据： A ．插入操作中依次输入 11 ， 12 ， 13 ， 14 ， 15 ， 16 ，生成一个单链表 B ．查找操作中依次输入 12 ， 15 ， 22 返回这 3 个元素在单链表中的位置 C ．删除操作中依次输入 2 ， 5 ，删除位于 2 和 5 的元素 3 ．概要设计 1 ）为了实现上述程序功能，需要定义单链表的抽象数据类型： ADT LinkList { 数据对象：D={ai|ai ∈ IntegerSet,i=0,1,2, … ,n,n ≥ 0} 数据关系：R={背包问题解法
密码技术竞赛测试题
《算法设计与分析》实验指导
回溯法实验(0-1背包问题)
信息学奥赛注意事项
实验二(贪心算法)
背包问题
数据结构课程设计实验大题
背包问题C语言程序设计
动态规划试题
数据结构之背包问题
数据结构与算法专题实验实验报告_八皇后_背包问题的求解_农夫过河
算法设计与分析 综合设计性实验(实验报告的要求)
动态规划法求解背包问题
2010计算机算法分析与设计任务书
算法实验二(题库)二
背包问题课程设计
数据结构实验参考与备选题目
相关主题
文本预览