en.wikipedia.org/wiki/Knapsack_problem
1 correction found
Besides, here we assume that x i > 0
This is not the standard unbounded knapsack assumption. In unbounded knapsack, each item count may be any non-negative integer, including 0; requiring x_i > 0 would wrongly force at least one copy of every item type.
Full reasoning
For the unbounded knapsack problem, the decision variable for each item type counts how many copies are taken, and standard formulations allow zero or more copies of each item. Writing x_i > 0 changes the problem: it would require taking at least one copy of every item type, which is not the unbounded knapsack problem and can even contradict optimal solutions where some item types are omitted entirely.
A standard integer-programming formulation uses x_j ∈ Z_{≥0} for every item type, i.e. each count is a non-negative integer. Likewise, MIT lecture material quoted below defines unbounded knapsack with x_i ∈ N_0 for all items. Those formulations directly contradict the claim that the section assumes x_i > 0.
So the issue is not merely notation: > 0 is mathematically different from ≥ 0, and the former misstates the feasible set of the unbounded knapsack problem.
2 sources
- Unbounded knapsack - Combinatorial Optimization · Fabio Furini
Using these variables, an Integer Linear Programming (ILP) model for the Unbounded Knapsack Problem (UKP) reads as follows: ... subject to Σ w_j x_j ≤ c ... x_j ∈ Z_{≥ 0}, ∀ j ∈ I.
- Faster Fully Polynomial Approximation Schemes for Knapsack Problems (MIT)
If there is no bound on the number of each item entirely, the resulting generalization is called the Unbounded Knapsack Problem. Unbounded Knapsack Problem ... x_i ∈ N_0 for all i ∈ N.