6
votes
Set of K elements with minimum cost and GCD=1
You can do this with dynamic programming. Let $S$ be the input set, and let $N=\max S$. We define the table $T\in\mathbb{N}^N$ where
$$
T[w] = \min_{\substack{X\subseteq S\\ \operatorname{gcd}(A[X])=w}...
- 4,662
3
votes
Most Efficient way to compute array
There is an easy $\mathcal{O}(n)$ solution in dynamic programming.
Consider the following functions:
$f_0(i)$ is the maximum sum without three consecutives values, up to index $i$, without the value $...
- 16.9k
3
votes
Set of K elements with minimum cost and GCD=1
This is NP-hard. We will prove this by reduction from the set cover problem.
Consider a set $U$, and a set $S$ of subsets of $U$. The set cover problem asks for the smallest subset of $S$ whose union ...
- 342
1
vote
Do all recursive problems have optimal substructure?
All problems with an optimal substructure can be solved recursively, but not all problems that can be solved with recursion have an optimal substructure. I think you understand the first part of that ...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible