(转载) 数组a[]={3,5,2,4,1,8},要求从a中找出所有“和”等于10的子集
2024-10-11 17:34:33
背包问题。
不过就这道题目本身而言,由于集合a中只要6个元素,而不是成千上万,所以可以使用更直观的办法:
只要你能通过程序给出数组a中元素所组成的集合的所有的子集合(幂集),那么只需在这些集合中搜索等于10的就可以了。
而6个元素构成的集合的幂集可以通过6位二进制数来表示,对于从0到2的6次方减1(63)之间的所有的数,让其每一位比特位代表一个元素,当该位为0时
表示该数所表示的子集中没有这个元素,否则表示拥有这个元素,这样就能对应出所有的组合,然后在这些所有的组合中检测和是否为10就可以了。
#include <stdio.h> #define ARRAY_SIZE 6
#define MAX_NUM (1<<ARRAY_SIZE)
int main()
{
int i, j;
int sum;
int a[ARRAY_SIZE] = {,,,,,};
int count = ; for(i = ; i < MAX_NUM; i++)
{
sum = ;
for(j = ; j < ARRAY_SIZE; j++)
{
if(i & ( << j))
sum += a[j];
} if( == sum)
{
printf("%d: ", ++count);
for(j = ; j < ARRAY_SIZE; j++)
{
if(i & ( << j))
printf("%d + ", a[j]);
}
printf("\b\b= 10.\n");
}
}
printf("\nTotal: %d.\n", count); return ;
}
来源:http://xiaozunyan.blog.sohu.com/3534370.html
最新文章
- 《CPU的工作过程》
- jQuery学习笔记(三)jQuery中的事件
- JavaScript中面向对象的的深拷贝和浅拷贝
- Linux的一些常用快捷键和基本命令
- 关于C语言中的转义字符
- ORA-25154/ORA-01748
- 通过 BitNami 轻松安装 Redmine
- hadoop小知识札记
- 在docker上运行.net core程序
- rk3128 通过串口控制 GPIO
- kali syn洪水攻击实例
- linux内存源码分析 - SLUB分配器概述
- 这5个实用技巧,教你设计出更好的App
- 在微信小程序中,如何实现下拉刷新(模拟刷新)
- c#FTP应用---windows iis
- KeyPress 和KeyDown 、KeUp之间的区别
- Python全栈开发之14、Javascript
- Join 与 CountDownLatch 之间的区别
- Topcoder SRM 698 Div1 250 RepeatString(dp)
- ORACLE不使用工具的情况下获取对象DDL