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 |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
