经典问题，求教！！！
题目：有13个数：2，2，3，5，5，8，8，16，16，22，22，28，28（总和是165）
要求：求所有相加值在1到164之间的组合，并把每个组合的值打印出来（只取其中的某几个[包括1格或者全部]相加，在同一次中这13个数字能用一次）
谢谢！
问题点数：100、回复次数：14Top
1 楼sandrowjw（我的小猫照片给弄坏了，心都碎了）回复于 2002-12-31 12:56:03 得分 0
是动态规划吧。Top
2 楼widewave（冯雨(历史事实)）回复于 2002-12-31 13:29:05 得分 0
没明白，直接用循环不就行了？Top
3 楼libi（风自吟）回复于 2002-12-31 13:33:20 得分 0
任意不多于12个数都可以嘛，有必要编程吗？Top
4 楼Firstbyte（尘飞扬）回复于 2002-12-31 14:41:37 得分 0
关注!!Top
5 楼heiqisi（绝爱生鱼片）回复于 2002-12-31 14:53:38 得分 0
是啊，意思我也明白，就是和组合问题而已。但是我想知道用程序怎么去实现它？谢谢！Top
6 楼thllllll（aro）回复于 2003-01-01 16:56:43 得分 0
多用循环！一步步来！Top
7 楼skygzj（）回复于 2003-01-02 12:02:09 得分 0
用递归和一个队列来实现，等我编好了给你Top
8 楼snjsj（漂泊着）回复于 2003-01-02 12:26:40 得分 0
可以用一个"标志尺"来解决，就是将一个数按照二进制位来考虑，这是汇编中很常用的，但是c也有强大的对位操作的能力，因此可以套用，很明显，一个位对应一个数之后(1取，0不取），那么是从0000000000001～1111111111111（这个数是退出标志，不取）。Top
9 楼boxban（冻酸梨）回复于 2003-01-02 14:34:26 得分 100
共8190种组合，耗时7秒
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
void create_node(int, int, int, int, int);
void create_tree(int, int);
void print_one(int level);
int stack[200];
int data[] = {0,2,2,3,5,5,8,8,16,16,22,22,28,28};
//0 只是用来填充
int main(int argc, char* argv[])
{
//按题意，只要不是13个数全部相加，不可能大于164,
//因此，循环中没有求和检查
time_t start,end;
time(&start);
for(int i = 1; i < 13; ++i)
create_tree(13, i);
time(&end);
cout << "time:" << (end-start) << endl;
return 0;
}
void create_tree(int n, int m)
{
int level = 0;
int parent_data = 0;
int children_num = n - m + 1;
stack[level] = parent_data;
create_node(n, m, parent_data, children_num, level);
}
void create_node(int n, int m, int parent_data, int children_num, int level)
{
if(level == m){
print_one(level);
return;
}
level++;
for(int i = 1; i <= children_num; i++){
stack[level] = parent_data + i ;
int tmp = n - m + 1 - stack[level] + level ;
create_node(n, m, stack[level], tmp, level);
}
}
void print_one(int level)
{
static int cnt = 1;
printf("[%3d]", cnt++);
for(int i = 1; i <= level; i++)
cout << data[stack[i]] << " ";
cout << endl;
return;
}
Top
10 楼fdz81（小鱼儿）回复于 2003-01-05 14:31:47 得分 0
这不就是排列组合：2^13-2=8190
Top
11 楼Chrisma（Chrisma）回复于 2003-01-06 16:34:40 得分 0
用动态规划好，免得计算时间太长Top
12 楼aivinok（黄伟灵）回复于 2003-01-06 18:16:46 得分 0
晕.Top
13 楼heiqisi（绝爱生鱼片）回复于 2003-01-11 10:56:38 得分 0
高手！Top
14 楼xjtufans（浮云）回复于 2003-01-11 11:11:17 得分 0
这个问题金山用来考试过。
我用的是循环来实现的。
不通用，代码很长，效率也不高。
不知道有什么好的办法？Top
