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 ?
No. of solutions of equation?
1
$\begingroup$
linear-algebra
combinatorics
-
0and what is $n$? – 2011-11-03
2 Answers
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.
-
0So 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]$