中兴面试题 01背包问题

背包问题就是包要满，但是01背包允许包不满

一，题目：输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数，使其和等于 m ,要求将其中所有的可能组合列出来。

二，解释：比如输入m=4 n=4 则输出为：4

1+3 而2+2不正确，因为重复输出数字了

中心思想：1）如果1+2+3+……+n<m 则不存在这个数

2）如果m<n 则应该让n=m //因为m--->n之间的数都已经大于m了 没必要再计算了

3）如果m=n 输出n

4）如果m>n 递归循环

源码采用原型：0-1背包问题

参考博客：http://blog.csdn.net/tianshuai11/article/details/7025464

三，源码：（类似源码五）

#include<list>

#include<iostream> using namespace std; list<int> list1; void find_factor(int sum, int n) { // 递归出口 if(n <= 0 || sum <= 0) return; // 输出找到的结果 if(sum == n) { // 反转list list1.reverse(); for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++) cout << *iter << " + "; cout << n << endl; list1.reverse(); } list1.push_front(n); //典型的01背包问题 find_factor(sum-n, n-1); //放n，n-1个数填满sum-n list1.pop_front(); find_factor(sum, n-1); //不放n，n-1个数填满sum } int main() { int sum, n; cout << "请输入你要等于多少的数值sum:" << endl; cin >> sum; cout << "请输入你要从1.....n数列中取值的n：" << endl; cin >> n; cout << "所有可能的序列，如下：" << endl; find_factor(sum,n); return 0; }