City has $1, ..., n$ citizens. Citizen $c_{i}$ has $v_{i}$ number of votes and each citizen's vote can be bought for certain price $p_{i}$. Election can be won by getting at least half of the votes. Given $F$ funds and knowing that each not bribed person will vote against, can election be won?
I have to show this problem is NP-Complete.
My idea is to just get maximum ammount of votes by using knapsack algorithm and checking if result (value of packed items) $R \gt \frac{1}{2}\sum_{v\in{V}}^{} v$, but i don't know if this is the right thinking, and what's more I have no idea how to show it formally and properly.
The decision version of the Knapsack problem is:
Knapsack: Given $n$ items with
$\quad$ sizes $\quad\;\;s_1, s_2, ..., s_n$
$\quad$ values $\quad v_1, v_2, ..., v_n$
$\quad$ capacity $\;B$
$\quad$ value $\quad\; V$
is there a subset $S \subseteq \{ 1, 2,..., n \}$ such that $\sum_{i \in S} s_i \leq B$ and $\sum_{i \in S} v_i \geq V?$
Election: Given $n$ citizens with
$\quad$ sizes (prices)$\quad\quad\quad\quad\quad\; p_1, p_2, ..., p_n$
$\quad$ values (number of votes) $\;v_1, v_2, ..., v_n$
$\quad$ capacity (funds) $\quad\quad\quad \; F$
$\quad$ value (half the votes) $\quad\;V=\frac{1}{2} \sum_{i = 1}^{n} v_i$
is there a subset $S \subseteq \{ 1, 2,..., n \}$ such that $\sum_{i \in S} p_i \leq F$ and $\sum_{i \in S} v_i \geq V?$
Can you see the correspondence between the 2 decision problems now?