转载的文章,原链接
http://www.cnblogs.com/pippo0725/articles/2046366.html
#include <iostream>
using namespace std;
int length;
void PrintSolutions(int *flag)
{
for (int i=0; i<length; i++)
{
if (flag[i] == 1)
{
cout << i+1 << " ";
}
}
cout << endl;
}
void BagProblem(int m, int n, int *flag)
{
if(n<1 || m<1)
return;
if(m < n)//如果m小于n,则从m+1到n肯定不能在取出数的集合中,不作考虑
{n = m;}
if (n == m)
{
flag[n-1] = 1;
PrintSolutions(flag);
flag[n-1] = 0;
}
flag[n-1] = 1;
BagProblem(m-n, n-1, flag);//将n放入,对前n-1个数递归求加和等于m-n的
flag[n-1] = 0;
BagProblem(m, n-1, flag);//不放入n,对前n-1个数递归求加和等于m的
}
int main(int argc, char* argv[])
{
int m, n;
cout << "Please input the m and n:" << endl;
cin >> m >> n;
cout << "The solution is:" << endl;
length = n;
int *flag = (int *)malloc(sizeof(int)*n);
memset(flag, 0, sizeof(flag));
BagProblem(m,n,flag);
//delete flag;//这个地方犯了一个原则性的错误 new和delete成对使用, malloc应该和free成对使用,要不然就会造成内存泄露
free(flag);
return 0;
}
这道题的思路参考0-1背包:定义函数F(n,m)来求解这个问题,那么F(n,m)可以分解为两个子问题F(n-1,m)和F(n-1,m-n).
代码的亮点应该就是flag数组的使用,充分利用了递归的性质,只是很简单的一个数组就完成了所有组合的输出。在每次把flag[i]设置为1之后就进入递归,代表了将i放入背包,当退出递归函数的时候,肯定要将flag[i]赋为0,因为这时候i已经不在背包中了。
分享到:
相关推荐
编程求解:输入两个整数 n 和 m,从数列 1,2,3.......n 中随意取几个数,使其和等于m ,要求将其中所有的可能组合列出来。
1.5.6. 输入两个整数 n 和 m,从数列 1,2,3.......n 中 随意取几个数 ....... 116 1.5.7. 输入一个表示整数的字符串,把该字符串转换成整数并输出.............. 118 1.5.8. 给出一个数列,找出其中最长的单调...
0-1背包问题:输入两个整数n和m,从数列1,2,3....n中随意取几个数,使得其和等于m,求所有组合
给定一个整数数组,其中元素的取值范围为0到10000,求其中出现次数最多的数。
编写一个函数,根据给定的正整数n,返回斐波那契数列中第n个数字的值。 斐波那契数列是一个数列,每个数字都是前两个数字的和。数列的前两个数字是0和1。数列的前几项是:0, 1, 1, 2, 3, 5, 8, 13, 21, ...
题目:输入两个正整数m和n,求其最大公约数和最小公倍数。 1.程序分析:利用辗除法。 【程序7】 题目:输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1.程序分析:利用while语句,条件为...
如果已知一个序列中最长的不下降子序列长度,那么这个序列前面添加一个数之后的最长的不下降子序列长度可能加1,这与原来的最长不下降子序列中最大的两个数有关。 具体是,如果加的数比子序列最大值大,长度加1。...
20026 输入2个整数 num1 和 num2,计算并输出它们的和、差、积、商与余数。 4 第3周(M3) 5 20031 求1+2+3+......+100(调试示例error02_5) 5 20032 求m+(m+1)+(m+2)+......+100 5 20033 求1/m+1/(m+1)+1/(m+2)...
例2、设函数f(x)=log2x-logx2(0<x<1),数列{an}中的第n项an满足 (n=1,2,3,…). (1)求数列{an}的通项公式; (2)判断此数列的单调性. 解析: (1)由 , 即 , 由求根公式,并注意0<x<1,即 ,有an, 可得...
1、从弹框中,分两次输入两个数字,分别保存在 a 和 b中 2、如果 a 大于 b的话 ,则交换两个数字的位置 使用 短路&&,扩展赋值运算符,位运算 4、条件运算符(三目运算) 单目(一元)运算符 :++,--,! 双目(二元)...
JAVA应用程序设计上机报告包含以下几个实验,都是源程序。...A和B,A创建的对象可以计算两个正整数的最大公约数,B创建的对象可以计算两个数的最小公倍数。要求:B类中有一个成员变量是用A类声明;
题目题目描述输入两个整数 n 和 m,从数列1,2,3n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来输入描述:每个测试输入包含2个整数,n
题目:取一个整数a从右端开始的4~7位。 程序分析:可以这样考虑: (1)先使a右移4位。 (2)设置一个低4位全为1,其余全为0的数。可用~(~0 ) (3)将上面二者进行&运算。 【程序29】:用1、2、2、3、4、5这六个...
// I:1 // ':1 // m:3 // 空格:3 // g:2// ... String str = "I'm go to swimming"; Set<String> set = new HashSet(); for(int i=0;i<str.length();i++){ String s = str.substring(i,i+1); set....
取一个整数从右端开始的4~7位。 55.学习使用按位取反~ 56.用circle画圆形 57.学用line画直线 58.用rectangle画方形 59.画图综合例子 60.画图综合例子2 61.打印杨辉三角形 62.学习putpixel画点 63.画椭圆ellipse 64....
题目:输入两个正整数m和n,求其最大公约数和最小公倍数。 1.程序分析:利用辗除法。 【程序7】 题目:输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1.程序分析:利用while语句,条件为...
1、输入两个值,然后交换这两个值,并输出 2、求 1!+2!+...+7!的值 3、输入一个五位数,计算这个五位数各位之和。 4、求1——1000以内的水仙花数 5、求两个数的最大公约数和最小公倍数。 6、有两只兔子,每三个月...
把一个数拆分为几个数的和.cmd 把指定文件中的指定位置的数字相加.cmd 把秒转换为天小时分秒的格式.cmd 把首行和尾行互换.cmd 抛弃路径尾部指定层次的字符串.cmd 拼接相临的奇偶行文本内容.cmd 指定图片路径换桌面....
3.输入日期, 判断这一天是这一年的第几天? 4.打乱一个排好序的list对象alist? 数据类型 5.现有字典 d= {'a':24,'g':52,'i':12,'k':33}请按value值进行排序? 6.字典推导式 7.请反转字符串 "aStr"? 8.将字符串 "k:1...
83.两个整数之间所有的素数 84.路痴 85.冒泡排序 86.你会存钱吗 87.逆序整数 88.排列 89.排列分析 90.平均值函数 91.奇特的分数数列 92.求建筑高度 93.区间内素数 94.三点顺序 95.山迪的麻烦 96.删除字符 97.是该年...