snippetMinor
A little confusion with the Knapsack problem (a worked example)
Viewed 0 times
problemtheworkedwithexamplelittleconfusionknapsack
Problem
I'm going through a worked example on the Knapsack problem:
My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a fraction of 1 (otherwise it breaks the inequality) but why specifically $4/5$? Any insight is highly appreciated.
My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a fraction of 1 (otherwise it breaks the inequality) but why specifically $4/5$? Any insight is highly appreciated.
Solution
The (non-negative) variables $x_1,x_2,x_3,x_4$ must satisfy the constraint
$$ 2x_1+2x_2+4x_3+5x_4 \leq 8. $$
If $x_1=x_2=1$ then this simplifies to
$$ 4x_3+5x_4 \leq 4, $$
which implies in particular that $x_3 \leq 1$ and $x_4 \leq 4/5$ (since $x_3,x_4 \geq 0$).
$$ 2x_1+2x_2+4x_3+5x_4 \leq 8. $$
If $x_1=x_2=1$ then this simplifies to
$$ 4x_3+5x_4 \leq 4, $$
which implies in particular that $x_3 \leq 1$ and $x_4 \leq 4/5$ (since $x_3,x_4 \geq 0$).
Context
StackExchange Computer Science Q#41516, answer score: 3
Revisions (0)
No revisions yet.