1
$\begingroup$

Given an equation $a_1 X_1 + a_2 X_2 + \cdots + a_n X_n = N$ where $a_1,a_2,\ldots,a_n$ are positive constants and each $X_i$ can take only two values $\{0,1\}$. $N$ is a given constant. How can we calculate the possible no of solutions of given equation ?

  • 0
    Well in general the number of solutions depends on all your parameters, but do you need bounds on the number of solutions or something? i.e. the best way to know it is to dumbly compute all possibilities... but that's just not brilliant, isn't it.2011-11-03
  • 0
    @PatrickDaSilva : "the best way to know it is to dumbly compute all possibilities..." This is not a good idea since N is very large.2011-11-03
  • 0
    So what do you need actually? Bounds? Or the exact number of solutions? That could be reaaaally hard.2011-11-03
  • 0
    I need exact number of solutions.2011-11-03
  • 0
    do you know the $a_i$? Because the answer depends a lot on them, probably more than on $N$. For example, with $a_i=2^i$ a simple reasoning shows that the answer is either $0$ or $1$, depending on which is bigger: $N$ or $2^n$. While with $a_1=1,...,a_n=1$ you will get $n$ chose $N$ solutions. And i assume all your numbers are probably integers....2011-11-03
  • 0
    yes, each ai will be less than 15 and N < 10^18 .2011-11-03
  • 0
    and what is $n$?2011-11-03

2 Answers 2

2

This looks like the Knapsack Problem, which means there is no known general solution and there is unlikely to be one. Specifically, it is a hard problem to decide if there is even one solution. If all $a_i$ are equal, then it becomes simple.

  • 0
    So my guess that this was a very hard problem was indeed right. Thanks for the answers both of you, user981570 and Carl =)2011-11-03
2

This is counting the number of solutions to the knapsack problem. You can adapt the Dynamic Programming algorithm to do this in pseudopolynomial time. (I'm assuming the input data are integers.) Let $s[i,w]$ = # of ways to achieve the sum $w$ using only the first $i$ variables. Then $$s[0,w]=\begin{cases}1 & w=0 \\0 & w \ne 0\end{cases}$$ For $i=1\ldots n$, For $w=0\ldots N$ $$s[i,w] = s[i-1,w] + s[i-1,w-a_i]$$