Question

背包问题 数据结构C语言版

Answer 1

.我给你说个思路
这些组合可以用0-2^n个数字表示
例如 只有W1是00000……1（2进制）
全选是11111111……1（2进制）
所以你用一个while循环
从0到2^n遍历一般 就做出来了

追问

那回溯怎么做呢

追答

不用回溯啊
double weight =0;
double W[n]={W1,W2……Wn};
int i,j,flag;
flag=0;
int binary[n];
i=2^n;
j=0;
while（j<i）
{
binary[n]={0};
if(j&1)
{
weight+=W[0];
binary[0]=1;
}
if(j&2)
{
weight+=W[1];
binary[1]=1;
}
……
if(j&2^(n-1))
{
weight+=W[n-1];
binary[n-1]=1;
}
if(weight==T)
{
if(flag==0)
flag=1;
输出binary数组
}
j++;
}
if(flag==0)
输出无解

够清楚了么