哪怕所有的都瞧不起的一个人，你也不要轻视，轻易的下结论的人是轻率的、轻浮的，是做不了大事的！
问题：找出数组的所有子集，要求子集的所有元素和为一定值，如{1,2,3,4,5,8}有子集{1,2,3,4}、{2,8}等。 分析：这是一个求部分自己的问题，可以参考上张百鸡问题的求解，但是循环的次数太多这样做不太好，考虑别的方法；记得linux内核中有关于位向量的操作，这里打算用位向量做做，呵呵，直接用stl中的bitset了。
1
2
/**//*************************************************************************
3
* Copyright (c) 2009
4* All rights reserved.
5*
6* 文件名称：bitset.cpp
7* 摘 要：子集问题
8*
9* 当前版本：1.0
10* 作 者：fighter
11* 完成日期：
12*
13
***************************************************************************/
14
15#include <stdint.h>
16#include <bitset>
17#include <iostream>
18
19using namespace std;
20
21int main( int argc, char ** argv)
22
{
23 int i, j;
24 int size = 0;
25 int sum = 23;
26 int tmp = 0;
27
28 bitset<64> bit;
29
30
int array[] = { 1, 2, 3, 4, 5, 8};
31
32 size = sizeof( array) / sizeof(int);
33
34 for( i = 0; i < 1 << size; i++)
35 {
36 bit = i;
37 tmp = 0;
38 for( j = 0; j < size; j++)
39 {
40 if( bit[j])
41 {
42 tmp += array[j];
43
}
44 }
45
46 if( tmp == sum)
47 {
48 for( j = 0; j < size; j++)
49 {
50 if( bit[j])
51 {
52 cout << array[j] << endl;
53 }
54 }
55 }
56 }
57
58 return 0;
59}
60
外层循环主要用来是数据的准备，如果每个元素都用的话就是二进制的形式 0x111111，是63，所以外层循环的控制那是 <1 <<size
posted on 2009-07-06 14:43
似水流年 阅读(1344)
评论(1) 编辑 收藏 引用 所属分类:
练手的小例子