题目:
输入两个整数n 和m,从数列1,2,3.......n 中随意取几个数,
使其和等于m ,要求将其中所有的可能组合列出来.
思路:在每一次递归中,考虑是与否将当前元素添加到数列中去,知道和达到某一值为止。
代码实现:
view plaincopy to clipboardprint?
#include<iostream>
#include<deque>
using namespace std;
void findNums(int n,int leftSum,deque<int>& deq)
{
if(n<0||leftSum<0)return; //已经遍历完数列,返回
if(leftSum>0)
{
deq.push_front(n); //将n加入数列或者不加入
findNums(n-1,leftSum-n,deq);
deq.pop_front();
findNums(n-1,leftSum,deq);
}
else { //当前数列综合已经达到要求,则输出
deque<int>::iterator i=deq.begin();
for(;i!=deq.end();++i)
{
cout<<*i<<" ";
}
cout<<endl;
}
}
int main()
{
deque<int> myDeq;
findNums(10,35,myDeq);
return 0;
}
同类题目:
题目:输入一个已经按升序排序过的数组和一个数字,
在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组1、2、4、7、11、15 和数字15。由于4+11=15,因此输出4 和11。
思路:对于这道题只要增加一个数组的记录就行了,其他一样。
同步博客:http://blog.csdn.net/moxiaomomo/archive/2011/05/24/6441831.aspx
分享到:
相关推荐
第一讲 01背包问题 这是最基本的背包问题,每个物品最多只能放一次。 第二讲 完全背包问题 第二个基本的背包问题模型,每种物品可以放无限多次。 第三讲 多重背包问题 每种物品有一个固定的次数上限。 第四讲 ...
背包问题(Knapsack Problem)是一个经典的组合优化问题,通常分为两种类型:0/1背包问题和分数背包问题。 1. **0/1背包问题**: - 给定一组物品,每个物品都有自己的重量和价值,要求在给定的背包容量下,选择...
背包问题九讲.pdf,详细的介绍各种类型的背包问题。
1 [斩尾行动]贪心算法实现哈夫曼编码; 2 用回溯法解决0-1背包问题;比较穷举法、动态规划法、贪心法实现的0-1背包...3 用回溯法编程实现装载问题,比较此装载问题与贪心法装载问题区别,思考不同算法的适用问题类型。
关于背包问题的九种类型,解析很透彻,01背包,多重背包,完全背包,二维背包等等。
名称:Knapsack 类型:可视化多重背包问题计算器 开发工具:vs2008 技术平台:C# 作者:FIA E-mail:iamfia@sina.com 完全开源 仅供参考
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
易语言写的魔兽世界背包物品遍历源码,背包物品所在背包,物品ID,物品名称,物品数量,物品品质,物品类型,物品等级。附:易语言超级模块8.0
背包九讲里面讲述了九种不同的背包类型,对于想学背包的人来说,这是一个不错的选择!
在背包栏和装备栏中设置用于记录当前绑定图片的类型然后每次点击背包栏或者装备栏中的一个按钮则将按钮的图片,然后把对应的精灵按照mouse_type设置在那个图片UI控件上,并让图片跟随鼠标移动,实现装备的切换效果。...
农夫背包问题完整解答,采用C++编写,包含完整工程(源代码,头文件,可执行文件,输入文件等),运用栈(回溯)求解。 运用模板,稍作修改即可用于不同类型数据。 工程采用Visual Studio 2008编译、运行,但头文件...
针对目前尚无多维多选择背包问题(MMKP)高效核算法的现状,提出用多种方法来构造处理这种类型背包的核。首先论述了如何在一般背包问题中获得核;接着根据事先设定的度量指标详细讨论了MMKP的基本解和两种排序关系,并...
动态规划之背包九讲,属于动态规划基础类型,详细讲解了各种背包问题
分枝定界法是一个用途十分广泛的算法,运用这种算法的技巧性很强,不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索。
包括0-1背包、无限背包、有限背包、有价值背包、小数背包(贪心即可)等,是极为经典的模型,其转化与优化也是很重要的。 2、最长非降子序列模型 改版:渡河问题、合唱队型等 3、最大子段和模型 改版:K大子段和、...
资源名:求解背包问题的离散粒子群算法程序_采用0-1二进制编码_可以直接运行_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行...
抽象的针对1-0无界背包问题的经典动态编程算法已扩展为使用有理数,并且具有任意数量的独立维。 在多项式时间内解决了特殊情况,并将其用作新分区算法的一部分。 等子问题复杂度的算法被改进为仅在分区数量上是指数...
手提包分类数据集,它包含5种不同类型的手提包,包括:背包迷你、带包、大包、肩包、大手提袋,每个类别(即手提包类型)包含550张图片,所有类别的图片数量相等。手提包分类数据集,它包含5种不同类型的手提包,包括...
尖叫背包概述用于处理远程和本地数据资源同步的实用程序。 开发用于 CheckM 但希望足够通用以用于其他地方。安装应该很简单 pip install ScreamingBackpack示例用法该实用程序的工作原理是在数据目录中放置一个小...
以下是一些常见类型的管理系统: 学校管理系统: 用于学校或教育机构的学生信息、教职员工信息、课程管理、成绩记录、考勤管理等。学校管理系统帮助提高学校的组织效率和信息管理水平。 人力资源管理系统(HRM):...