1
The problem is NP-hard, by a reduction from 3-dimensional matching. For each triplet $(x,y,z)$ in the 3-dimensional matching problem, we have items $x_1$, $y_2$, $z_3$ and set the group of 3 items $(x_1,y_2,z_3)$ to have value $1$ and weight 0. Each individual item has value $0$ and weight $+\infty$. Now the solution to your knapsack problem yields a ...
1
Yes, you can. As Dmitry explains, CYK parsing can be used to parse a linear grammar in $O(n^2)$ time, where $n$ is the length of the input word.
CYK parsing is a dynamic programming algorithm that sets $P[l,s,R]$ to be true if $a_{s .. s+l-1}$ can be generated from the non-terminal $R$, where $a_{1..n}$ is the input word.
Note that there is a recurrence ...
Only top voted, non community-wiki answers of a minimum length are eligible
