Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Say I want to fill a knapsack with as many things as possible. I don't care about what they are, simply the number. But I don't want the total weight to exceed a set limit.
[https://qiskit.org/textbook/ch-applications/qaoa.html#1.-Constructing-Problem-Hamiltonian-]
Thanks
The goal of the knapsack problem is to pick items such that the total value of the knapsack is maximized subject to the knapsack weight constraint. This already implies that your cost function has nothing to do with weights but values of each individual item.
I suggest first reading Wikipedia or some other resources before posting such questions.
Since your questions (1) and (2) are clearly explained and illustrated with pictures on Wikipedia, I will not bother answering that.
As for your question (3), if you read the Wikipedia page, you will immediately see that the knapsack constraint is an inequality constraint. This means you will need extra qubits to incorporate it into a Hamiltonian as a penalty term.
The short answer is that you need about $n + \log_2(W) + 1$ qubits, in general. Here, $n$ is the number of variables (knapsack items), and $W$ is the constraint bound.
