Knapsack Problem with Equal Weights
up vote
0
down vote
favorite
The problem consists in the standard knapsack problem in interger programming with the weights that all have the same values, for example they are all equal to one.
It seems to me that the solution of this problem should be trivial, that is first set to one the variable with the highest profit, then the one with the second highest profit and so on, until the knapsack is full.
I was wondering if there is a formal way to prove that this procedure reaches a global minimum, or if there are papers that deal with this particular instance of the knapsack problem.
Thank you.
optimization integer-programming
asked Nov 13 at 22:42
Vittorio Latorre
82
add a comment |
up vote
0
down vote
favorite
The problem consists in the standard knapsack problem in interger programming with the weights that all have the same values, for example they are all equal to one.
It seems to me that the solution of this problem should be trivial, that is first set to one the variable with the highest profit, then the one with the second highest profit and so on, until the knapsack is full.
I was wondering if there is a formal way to prove that this procedure reaches a global minimum, or if there are papers that deal with this particular instance of the knapsack problem.
Thank you.
optimization integer-programming
asked Nov 13 at 22:42
Vittorio Latorre
82
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
The problem consists in the standard knapsack problem in interger programming with the weights that all have the same values, for example they are all equal to one.
It seems to me that the solution of this problem should be trivial, that is first set to one the variable with the highest profit, then the one with the second highest profit and so on, until the knapsack is full.
I was wondering if there is a formal way to prove that this procedure reaches a global minimum, or if there are papers that deal with this particular instance of the knapsack problem.
Thank you.
optimization integer-programming
asked Nov 13 at 22:42
Vittorio Latorre
82
The problem consists in the standard knapsack problem in interger programming with the weights that all have the same values, for example they are all equal to one.
It seems to me that the solution of this problem should be trivial, that is first set to one the variable with the highest profit, then the one with the second highest profit and so on, until the knapsack is full.
I was wondering if there is a formal way to prove that this procedure reaches a global minimum, or if there are papers that deal with this particular instance of the knapsack problem.
Thank you.
optimization integer-programming
optimization integer-programming
asked Nov 13 at 22:42
Vittorio Latorre
82
asked Nov 13 at 22:42
Vittorio Latorre
82
asked Nov 13 at 22:42
Vittorio Latorre
82
asked Nov 13 at 22:42
Vittorio Latorre
82
asked Nov 13 at 22:42
Vittorio Latorre
82
82
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Try proof by contradiction. Assume all weights are 1 and the knapsack capacity is $C$. Posit an optimal solution that includes at least one item not among the $C$ most valuable items, and prove that you can improve it (contradicting optimality).
answered Nov 18 at 4:19
prubin
1,320125
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Try proof by contradiction. Assume all weights are 1 and the knapsack capacity is $C$. Posit an optimal solution that includes at least one item not among the $C$ most valuable items, and prove that you can improve it (contradicting optimality).
answered Nov 18 at 4:19
prubin
1,320125
add a comment |
up vote
0
down vote
Try proof by contradiction. Assume all weights are 1 and the knapsack capacity is $C$. Posit an optimal solution that includes at least one item not among the $C$ most valuable items, and prove that you can improve it (contradicting optimality).
answered Nov 18 at 4:19
prubin
1,320125
add a comment |
up vote
0
down vote
up vote
0
down vote
Try proof by contradiction. Assume all weights are 1 and the knapsack capacity is $C$. Posit an optimal solution that includes at least one item not among the $C$ most valuable items, and prove that you can improve it (contradicting optimality).
answered Nov 18 at 4:19
prubin
1,320125
Try proof by contradiction. Assume all weights are 1 and the knapsack capacity is $C$. Posit an optimal solution that includes at least one item not among the $C$ most valuable items, and prove that you can improve it (contradicting optimality).
answered Nov 18 at 4:19
prubin
1,320125
answered Nov 18 at 4:19
prubin
1,320125
answered Nov 18 at 4:19
prubin
1,320125
answered Nov 18 at 4:19
prubin
1,320125
1,320125
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2997459%2fknapsack-problem-with-equal-weights%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
