难题！高手请进！类似背包但带余数

从1到16中选择若干个数，使其和的2进制低4位为0011（或者说其和除以16的余数为3）。
怎么做？

我用16次for循环。效率低死了。
有没有好的方法？
高手请指点。

15 个解决方案

#1

没看明白，是从1到16中取数求和后，用和去除16余3吗？
如果这样只要先求和再除不就行了

#2

是啊，使取出的数的和除以16的余数为3。
如：
取出4，7，8。（4＋7＋8）/16=1.........3

问题是取若干个数，事前是不知道个数和哪些数的。有办法么？

#3

怎么个若干法？
从基本数学面讲
方程a+2b+3c+...+16k=16m+3  ->a+2b+3c+...+15j=16m+3
必须要赋予a,b,c,...,j一定的规则，才可以公式推导。
另外，如果随机选择的话，可以采用微调法：
  1。随机选择16个数，分别代表1-16的个数
  2。求和（先乘后加），假设和为X
  3。（x-3）%16 = y
  4。（16-y）的个数加1
完。

#4

若干就是可能1个，可能2个。。。。。。

a+2b+3c+...+15j+16k=16m+3

a,b,c.....j,k不是0就是1
范围变小很多，能否用矩阵相乘求逆解决？但是多了个m答案不固定。
有办法吗？

#5

题目的理解不是很清楚，个人觉得是不是上面的16个数只能出现一次。
所以最大的就1+2+3+......+16=136；令s=136， s/16=8...8
所以满足条件的数应该有9个即0*16+3，1*16+3，2*16+3.....8*16+3；
将这些数再一一分解成小于16且没有相同的数字之和。

如果是这样的话就应该是数字分解的题目了。

#6

1.递归去做：
取一个数---满足输出---继续找下一个
---不满要求继续取下一个
2.全遍历1-16
看是否能满足要求

#7

1.递归去做：
取一个数---满足输出---继续找下一个
---不满要求继续取下一个
不取当前数
2.全遍历1-16
看是否能满足要求

#8

递归算法：
#include <stdio.h>

void Check(int a[],int n,bool st);

void main()
{
   int a[16];
   int n=1;
   for(int i=0;i<16;i++)
   {
      a[i]=0;
    }
    Check(a,n,false);
   Check(a,n,true);
}
void Check(int a[],int n,bool st)
{
    if(n>16)
    {
       return;
     }
    int b[16];
    int sum;
    for(int i=0;i<16;i++)
    {
       b[i]=a[i];
       sum+=b[i];
    }
    if(st)
    {
      b[n-1]=n;
      sum+=n;
    }
     if(sum%16==3)
     {
         for(int i=0;i<16;i++)
         {
             if(b[i]!=0)
              {
                printf("%d " ,b[i]);
               }
         }
         printf("\n");
      }
      Check(b,n+1,true);
      Check(b,n+1,false);
}

#9

帮你看了一下，觉得提高效率可以：
计算从16取1到16取8中余3和余5的情况，也就可以得出全部的情况了。

#10

觉得如果得到全部的数集好像没有什么意义。

你是要随机得到一组，可参照
  1。随机选择16个数，分别代表1-16的个数（0或1）
  2。求和（先乘后加），假设和为X
  3。（x-3）%16 = y
  4。（16-y）的个数加1或y的个数减1或重新选择随机数

如果要统计个数的话，计算一下全集在[1，136]中的分布，肯定是有数学规律的。
推导出数学公式，即可计算和为任意值时的数集个数。（至于如何推导，分太少了啊）
然后根据newpuple(开始新的学程) ( ) 的方法求出。。。

#11

我的背包(至于(%16==3)，我就不说了

int function(int nSum, int nMax);
void function(int nBegin, int nEnd, int nValue);
void print();

int g_nCnt = 0;

int _tmain()
{
cout << function(7, 8) << endl;
return 0;
}

int g_Array[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

int function(int nSum, int nMax)
{
g_nCnt = 0;
function(1, nMax, nSum);
return g_nCnt;
}

void function(int nBegin, int nEnd, int nValue)
{
for (int i=nBegin; i<=nEnd; ++i) {
if (g_Array[i] == 0) {
continue;
}

if (i == nValue) {
g_Array[i] = 0;
print();
g_Array[i] = i;

g_nCnt++;
return;
}
else if (i < nValue) {
g_Array[i] = 0;
function(i, nEnd, nValue - i);
g_Array[i] = i;
}
else {
return;
}
}
}

void print()
{
for (int i=0; i<sizeof(g_Array)/sizeof(int); ++i) {
if (g_Array[i] == 0) {
cout << i << ", ";
}
}

cout << endl;
}

#12

与背包相比没有什么区别

背包是总容量固定，现在也是类似的，总容量根据当前的和在动态的变化

比如，目前的总和是 16n + k, n是整数，k为0到15
如果k等于3就完成了任务

如果k小于3那么，背包的总数值就是16n+3
如果k大于3那么，背包的总数值就是16（n+1）+3

#13

其实就是找出1 到这些数的总和 16*(1+16)/2 之间，与 16 相除余 3 的那些数嘛

(1) 找出这些数里头与16相除余3的数，比如3、19、35等等，也就是 16n+3
       for(i=3;i<=16*(1+16)/2;i++)
       {
            if(i%16==3) x[j++]=i;
       }
(2) 如果需要继续划分由哪些数构成的话，再把x[j++]拆开就行了。

#14

你这样效率太低了

#15

终极优化版本，请高手检查有没有错误：
#define N 16
int stack[N];
int top = 0;
void comb( int i, int sum )
{
if( sum % 16 == 3 )
{
for( int j = 0; j < top; j++ )
{
cout<<stack[ j ]<<",";
}
}

for( int k = i+1; k < =N; k++ )
{
stack[ top++ ] = k;
comb( k, sum+k );
top--;
}
}

void main()
{
   for(int begin=1; begin <=N; begin ++)
   {
comb(begin, begin )
    }
}

#1