Question

m个数里面取n个数的算法 （财富悬赏给得不多，但这是我所有了，跪求大牛帮帮忙）

这个算法网上找来的，好像有错呀
组合算法
本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标代表的数被选中，为0则没选中。
首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。

例如求5中选3的组合：
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5

假如在6个数中找3个，6个数是1,8,4,3,5,2.按照他的算法没找到1,4,5的组合呀。
这是我做的程序
#include<stdio.h>
#define maxsize 128
int array[maxsize]={0};
int sum=0;
int T,N,M;
int w[maxsize];

void packet(int n,int m)
{
int i,j,k,state;
int count=m-1,count1=m;
for(i=0;i<m;i++)
array[i]=1;
for(i=0;i<m;i++)
sum+=w[i];
if(sum==T)
{
for(j=0;j<m;j++)
printf("%d ",w[i]);
putchar('\n');
}
sum=0;
while(count1!=0)
{
i=M;
state=i;
while(i<N)
{
array[i]=1;
array[i-1]=0;
for(j=0;j<n;j++)
{
if(array[j]==1)
sum+=w[j];
}
if(sum==T)
{
for(j=0;j<n;j++)
{
if(array[j]==1)
printf("%d ",w[j]);
}
putchar('\n');
}
sum=0;
if(count>0)
{
i--;
count--;
}
else
{
i=i+m;
count=M-1;
}
}
count1--;
if(count1==0)
break;
N--;
for(k=0;k<N;k++)
array[k]=0;
M--;
for(k=0;k<M;k++)
array[k]=1;
}
}

void main()
{
int i,n;
printf("Please input package volume:\n");
scanf("%d",&T);
printf("Please input the quantity of the product:\n");
scanf("%d",&n);
printf("Please please input the volume of each product:\n");
for(i=0;i<n;i++)
{
scanf("%d",&w[i]);
}
N=n;
for(i=1;i<=n;i++)
{
M=i;
packet(n,i);
}
}

Answer 1

输入n，m。然后输入n个数（不同的，相同的算法有点改变）求n个数中选m个的组合数！采取的是递归的方法！
#include <iostream>
using namespace std;
#define maxn 11
int n,m; //n,中选m个的组合数
int rcd[maxn];
int num[maxn];
void init1()
{
int i,j,val;
for (i=0;i<n;i++)
{
scanf("%d",&num[i]);
}
}
void perm(int l,int p)
{
int i;
if(l==m)
{
for(i=0;i<l;i++)
{
printf("%d",rcd[i]);
if(i<l-1)
printf(" ");
}
printf("\n");
}
for(i=p;i<n;i++)
{
rcd[l]=num[i]; //在l的位置放上该数
perm(l+1,i+1);

}
}//perm

int main()
{
scanf("%d",&n);
scanf("%d",&m);
init1();
perm(0,0);
}

追问

非常非常感谢你，其实我是在做个课程设计（简单背包问题），我想求出所有组合（即是不规定几个数为一组），再看哪个组合刚好等于背包体积T就输出那个组合的。我很希望你教下我怎么改才能求所有组合。
现在我做好，只是我还看不懂这个算法而已。不管怎样，这个分还是给你的了。

追答

背包问题的话，有背包问题的解法！ 如果物品很多的话，你要求的他所有组合就很难实现了！当n超过30时，递归的时间就很长了，就无法实现了！
希望你能给你的问题的具体内容，给我看看！

追问

我用这个算法做出来，题目是输入背包体积T，再输入物品个数n和各个物品的体积。将物品放进背包使背包刚好装满，要求输出所有解。

追答

//帮你解决了不过用的是回溯，但也是递归的方法，比递归更实用点！
#include
using namespace std;
int goods[100];
bool flag[100];
int sum[100];
bool f(0);
int k(-1);
int knap(int s, int n) //s为当前背包总重量，n为物品的个数同时代表数组下标
{
int i;
if(s==0)
{
f=1;
for(i=k;i>=0;i--)
{
if(sum[i])
printf("%d ",sum[i]);
}
printf("\n");
return 0;
}
if(flag[n]==0)
{
for (i=n;i>=1;i--)
{
if(s>=goods[i])
{
flag[i]=1;
sum[++k]=goods[i];
knap(s-goods[i],i-1);
flag[i]=0;
--k;
}
}
}
return 1;
}
int main()
{

int bag_weight; //背包重量
int goods_num; //每组物品数量
int j,temp;
//打开文件
//freopen("input.txt","r",stdin);//文本输入
scanf("%d",&bag_weight);//读取背包重量
scanf("%d",&goods_num); //读取物品数量
f=0;
//memset(flag,0,sizeof(flag)); 初始化标记数组flag；
goods[0]=0; //将goods[0]赋值为0，为后面递归做准备
for (j=1; j<=goods_num; j++)
{
//读取本组每个物品的重量，放入数组中
scanf("%d",&temp);
goods[j]=temp;
}
knap(bag_weight,goods_num);
if(!f)//没有合适的情况
printf("NO solution\n");

return 0;
}

Answer 2

SB

追问

你可以说我2B，但我不喜欢别人叫我SB。fuck you!!!

Answer 3

m,