Proof that the fractional knapsack problem exhibits the greedy-choice property
$begingroup$
I have the following problem:
Prove that the fractional knapsack problem has the greedy-choice property.
The greedy choice property should be the following:
An optimal solution to a problem can be obtained by making local best choices at each step of the algorithm.
Now, my proof assumes that there's an optimal solution to the fractional knapsack problem that does not include a greedy choice, and then tries to reach a contradiction.
Proof
Assume there's an optimal solution $A = { a_1, a_2, ... , a_n}$ to the fractional knapsack problem ($F$) that does not include the item $i$, with the greatest value per weight $(frac{v}{w})$ ratio of all initial items.
Suppose $a_1$ is the item in the solution $A$ with the greatest value per weight ratio. Note that we have $$frac{v_i}{w_i} geq frac{v_{a_1}}{w_{a_1}}$$
Now, suppose we remove $a_1$ from $A$ and we obtain a solution $A'$ to a subproblem $F'$: $$A' = A - a_1$$
If we combine the solution $A'$ (to the subproblem $F'$) with the greedy choice $i$ (or a fraction of it), we will obtain a greater (or equal) valuable solution $B$, since $$frac{v_i}{w_i} geq frac{v_{a_1}}{w_{a_1}}$$
If $B$ is better than $A$, then this is a contradiction, and thus $i$ must be included; if $B = A$, then we have shown that the greedy choice is included anyway, since that would mean that $frac{v_i}{w_i} = frac{v_{a_1}}{w_{a_1}}$
Is my proof correct? If not, why, or how can I improve it?
proof-verification algorithms proof-writing
$endgroup$
|
show 2 more comments
$begingroup$
I have the following problem:
Prove that the fractional knapsack problem has the greedy-choice property.
The greedy choice property should be the following:
An optimal solution to a problem can be obtained by making local best choices at each step of the algorithm.
Now, my proof assumes that there's an optimal solution to the fractional knapsack problem that does not include a greedy choice, and then tries to reach a contradiction.
Proof
Assume there's an optimal solution $A = { a_1, a_2, ... , a_n}$ to the fractional knapsack problem ($F$) that does not include the item $i$, with the greatest value per weight $(frac{v}{w})$ ratio of all initial items.
Suppose $a_1$ is the item in the solution $A$ with the greatest value per weight ratio. Note that we have $$frac{v_i}{w_i} geq frac{v_{a_1}}{w_{a_1}}$$
Now, suppose we remove $a_1$ from $A$ and we obtain a solution $A'$ to a subproblem $F'$: $$A' = A - a_1$$
If we combine the solution $A'$ (to the subproblem $F'$) with the greedy choice $i$ (or a fraction of it), we will obtain a greater (or equal) valuable solution $B$, since $$frac{v_i}{w_i} geq frac{v_{a_1}}{w_{a_1}}$$
If $B$ is better than $A$, then this is a contradiction, and thus $i$ must be included; if $B = A$, then we have shown that the greedy choice is included anyway, since that would mean that $frac{v_i}{w_i} = frac{v_{a_1}}{w_{a_1}}$
Is my proof correct? If not, why, or how can I improve it?
proof-verification algorithms proof-writing
$endgroup$
$begingroup$
You say that item $i$ has the smallest value per weight ratio and $a1$ has the largest. In that case the inequalities are the reverse of what you wrote.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 13:44
$begingroup$
@MichaelTiemann Sorry, for $i$, I meant the item with greatest value per weight ratio (not the smallest) of the original items...
$endgroup$
– nbro
Aug 19 '15 at 13:49
$begingroup$
The proof is not very convincing because (1) it does not explain how all the other choices influence the answer, and (2) it does not treat the specific mathematics of the fractional knapsack problem, namely, that at any given point in the construction of the objective function, an infinitesimal (weight) quantity of a suboptimal choice can be replaced by an equal weight quantity of the greedy choice, until the weight quantity of the greedy choice is exhausted.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:12
$begingroup$
Well, since this problem exhibits optimal substructure, then for your first point my proof should give an answer... not sure if I understood your second point...
$endgroup$
– nbro
Aug 19 '15 at 14:16
$begingroup$
Replacing the previously best choice with the newly best choice is not optimal. You want to replace the previously worst choice with the newly best choice to be optimal, as the following answer shows.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:47
|
show 2 more comments
$begingroup$
I have the following problem:
Prove that the fractional knapsack problem has the greedy-choice property.
The greedy choice property should be the following:
An optimal solution to a problem can be obtained by making local best choices at each step of the algorithm.
Now, my proof assumes that there's an optimal solution to the fractional knapsack problem that does not include a greedy choice, and then tries to reach a contradiction.
Proof
Assume there's an optimal solution $A = { a_1, a_2, ... , a_n}$ to the fractional knapsack problem ($F$) that does not include the item $i$, with the greatest value per weight $(frac{v}{w})$ ratio of all initial items.
Suppose $a_1$ is the item in the solution $A$ with the greatest value per weight ratio. Note that we have $$frac{v_i}{w_i} geq frac{v_{a_1}}{w_{a_1}}$$
Now, suppose we remove $a_1$ from $A$ and we obtain a solution $A'$ to a subproblem $F'$: $$A' = A - a_1$$
If we combine the solution $A'$ (to the subproblem $F'$) with the greedy choice $i$ (or a fraction of it), we will obtain a greater (or equal) valuable solution $B$, since $$frac{v_i}{w_i} geq frac{v_{a_1}}{w_{a_1}}$$
If $B$ is better than $A$, then this is a contradiction, and thus $i$ must be included; if $B = A$, then we have shown that the greedy choice is included anyway, since that would mean that $frac{v_i}{w_i} = frac{v_{a_1}}{w_{a_1}}$
Is my proof correct? If not, why, or how can I improve it?
proof-verification algorithms proof-writing
$endgroup$
I have the following problem:
Prove that the fractional knapsack problem has the greedy-choice property.
The greedy choice property should be the following:
An optimal solution to a problem can be obtained by making local best choices at each step of the algorithm.
Now, my proof assumes that there's an optimal solution to the fractional knapsack problem that does not include a greedy choice, and then tries to reach a contradiction.
Proof
Assume there's an optimal solution $A = { a_1, a_2, ... , a_n}$ to the fractional knapsack problem ($F$) that does not include the item $i$, with the greatest value per weight $(frac{v}{w})$ ratio of all initial items.
Suppose $a_1$ is the item in the solution $A$ with the greatest value per weight ratio. Note that we have $$frac{v_i}{w_i} geq frac{v_{a_1}}{w_{a_1}}$$
Now, suppose we remove $a_1$ from $A$ and we obtain a solution $A'$ to a subproblem $F'$: $$A' = A - a_1$$
If we combine the solution $A'$ (to the subproblem $F'$) with the greedy choice $i$ (or a fraction of it), we will obtain a greater (or equal) valuable solution $B$, since $$frac{v_i}{w_i} geq frac{v_{a_1}}{w_{a_1}}$$
If $B$ is better than $A$, then this is a contradiction, and thus $i$ must be included; if $B = A$, then we have shown that the greedy choice is included anyway, since that would mean that $frac{v_i}{w_i} = frac{v_{a_1}}{w_{a_1}}$
Is my proof correct? If not, why, or how can I improve it?
proof-verification algorithms proof-writing
proof-verification algorithms proof-writing
edited Aug 19 '15 at 13:50
nbro
asked Aug 19 '15 at 13:08
nbronbro
2,46163475
2,46163475
$begingroup$
You say that item $i$ has the smallest value per weight ratio and $a1$ has the largest. In that case the inequalities are the reverse of what you wrote.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 13:44
$begingroup$
@MichaelTiemann Sorry, for $i$, I meant the item with greatest value per weight ratio (not the smallest) of the original items...
$endgroup$
– nbro
Aug 19 '15 at 13:49
$begingroup$
The proof is not very convincing because (1) it does not explain how all the other choices influence the answer, and (2) it does not treat the specific mathematics of the fractional knapsack problem, namely, that at any given point in the construction of the objective function, an infinitesimal (weight) quantity of a suboptimal choice can be replaced by an equal weight quantity of the greedy choice, until the weight quantity of the greedy choice is exhausted.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:12
$begingroup$
Well, since this problem exhibits optimal substructure, then for your first point my proof should give an answer... not sure if I understood your second point...
$endgroup$
– nbro
Aug 19 '15 at 14:16
$begingroup$
Replacing the previously best choice with the newly best choice is not optimal. You want to replace the previously worst choice with the newly best choice to be optimal, as the following answer shows.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:47
|
show 2 more comments
$begingroup$
You say that item $i$ has the smallest value per weight ratio and $a1$ has the largest. In that case the inequalities are the reverse of what you wrote.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 13:44
$begingroup$
@MichaelTiemann Sorry, for $i$, I meant the item with greatest value per weight ratio (not the smallest) of the original items...
$endgroup$
– nbro
Aug 19 '15 at 13:49
$begingroup$
The proof is not very convincing because (1) it does not explain how all the other choices influence the answer, and (2) it does not treat the specific mathematics of the fractional knapsack problem, namely, that at any given point in the construction of the objective function, an infinitesimal (weight) quantity of a suboptimal choice can be replaced by an equal weight quantity of the greedy choice, until the weight quantity of the greedy choice is exhausted.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:12
$begingroup$
Well, since this problem exhibits optimal substructure, then for your first point my proof should give an answer... not sure if I understood your second point...
$endgroup$
– nbro
Aug 19 '15 at 14:16
$begingroup$
Replacing the previously best choice with the newly best choice is not optimal. You want to replace the previously worst choice with the newly best choice to be optimal, as the following answer shows.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:47
$begingroup$
You say that item $i$ has the smallest value per weight ratio and $a1$ has the largest. In that case the inequalities are the reverse of what you wrote.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 13:44
$begingroup$
You say that item $i$ has the smallest value per weight ratio and $a1$ has the largest. In that case the inequalities are the reverse of what you wrote.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 13:44
$begingroup$
@MichaelTiemann Sorry, for $i$, I meant the item with greatest value per weight ratio (not the smallest) of the original items...
$endgroup$
– nbro
Aug 19 '15 at 13:49
$begingroup$
@MichaelTiemann Sorry, for $i$, I meant the item with greatest value per weight ratio (not the smallest) of the original items...
$endgroup$
– nbro
Aug 19 '15 at 13:49
$begingroup$
The proof is not very convincing because (1) it does not explain how all the other choices influence the answer, and (2) it does not treat the specific mathematics of the fractional knapsack problem, namely, that at any given point in the construction of the objective function, an infinitesimal (weight) quantity of a suboptimal choice can be replaced by an equal weight quantity of the greedy choice, until the weight quantity of the greedy choice is exhausted.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:12
$begingroup$
The proof is not very convincing because (1) it does not explain how all the other choices influence the answer, and (2) it does not treat the specific mathematics of the fractional knapsack problem, namely, that at any given point in the construction of the objective function, an infinitesimal (weight) quantity of a suboptimal choice can be replaced by an equal weight quantity of the greedy choice, until the weight quantity of the greedy choice is exhausted.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:12
$begingroup$
Well, since this problem exhibits optimal substructure, then for your first point my proof should give an answer... not sure if I understood your second point...
$endgroup$
– nbro
Aug 19 '15 at 14:16
$begingroup$
Well, since this problem exhibits optimal substructure, then for your first point my proof should give an answer... not sure if I understood your second point...
$endgroup$
– nbro
Aug 19 '15 at 14:16
$begingroup$
Replacing the previously best choice with the newly best choice is not optimal. You want to replace the previously worst choice with the newly best choice to be optimal, as the following answer shows.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:47
$begingroup$
Replacing the previously best choice with the newly best choice is not optimal. You want to replace the previously worst choice with the newly best choice to be optimal, as the following answer shows.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:47
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
The proof is by induction.
To pack a fractional knapsack with a single item $a_1$, fill the knapsack to the limit of either the total capacity of the knapsack or the total quantity of $a_1$ available, whichever is less.
Given a fractional knapsack with total weight capacity $W$, and optimally packed with $A = {a_1, a_2, ..., a_n}$, values $V = {v_1, v_2, ..., v_n}$ with weight quantities $W = {w_1, w_2, ..., w_n}$ and a new choice $a_{n+1}$, value $v_{n+1}/w_{n+1} > v_i/w_i$ for all $i in 1...n$ and available weight $w_{n+1}$, then a new optimal solution can be found as follows. Let $j_1$ be the index such that $v_{j_1} / w_{j_1} < v_i / w_{j_1}$ for all $i in 1...n$ and $i neq j_1$. If we replace $a_{j_1}$ with $a_{n+1}$, the objective function improves by $(v_{n+1} - v_{j_1}) / min(w_{n+1},w_{j_1})$. This is the largest possible increase in the objective function because any other replacement choice subtracts a larger amount than $v_{j_1} / min(w_{n+1},w_{j_1})$. We continue this replacement strategy, choosing $j_k$ as the index of the remaining item with the lowest value-to-weight ratio of the remaining items and replacing it entirely with $w_{j_k}$ of $a_i$ or with as much $a_i$ as remains. When the knapsack is completely full of $a_i$ or all available $a_i$ has been placed in the knapsack, we have an optimal solution, achieved by being as greedy as possible with the choice $a_i$.
QED
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f1402668%2fproof-that-the-fractional-knapsack-problem-exhibits-the-greedy-choice-property%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The proof is by induction.
To pack a fractional knapsack with a single item $a_1$, fill the knapsack to the limit of either the total capacity of the knapsack or the total quantity of $a_1$ available, whichever is less.
Given a fractional knapsack with total weight capacity $W$, and optimally packed with $A = {a_1, a_2, ..., a_n}$, values $V = {v_1, v_2, ..., v_n}$ with weight quantities $W = {w_1, w_2, ..., w_n}$ and a new choice $a_{n+1}$, value $v_{n+1}/w_{n+1} > v_i/w_i$ for all $i in 1...n$ and available weight $w_{n+1}$, then a new optimal solution can be found as follows. Let $j_1$ be the index such that $v_{j_1} / w_{j_1} < v_i / w_{j_1}$ for all $i in 1...n$ and $i neq j_1$. If we replace $a_{j_1}$ with $a_{n+1}$, the objective function improves by $(v_{n+1} - v_{j_1}) / min(w_{n+1},w_{j_1})$. This is the largest possible increase in the objective function because any other replacement choice subtracts a larger amount than $v_{j_1} / min(w_{n+1},w_{j_1})$. We continue this replacement strategy, choosing $j_k$ as the index of the remaining item with the lowest value-to-weight ratio of the remaining items and replacing it entirely with $w_{j_k}$ of $a_i$ or with as much $a_i$ as remains. When the knapsack is completely full of $a_i$ or all available $a_i$ has been placed in the knapsack, we have an optimal solution, achieved by being as greedy as possible with the choice $a_i$.
QED
$endgroup$
add a comment |
$begingroup$
The proof is by induction.
To pack a fractional knapsack with a single item $a_1$, fill the knapsack to the limit of either the total capacity of the knapsack or the total quantity of $a_1$ available, whichever is less.
Given a fractional knapsack with total weight capacity $W$, and optimally packed with $A = {a_1, a_2, ..., a_n}$, values $V = {v_1, v_2, ..., v_n}$ with weight quantities $W = {w_1, w_2, ..., w_n}$ and a new choice $a_{n+1}$, value $v_{n+1}/w_{n+1} > v_i/w_i$ for all $i in 1...n$ and available weight $w_{n+1}$, then a new optimal solution can be found as follows. Let $j_1$ be the index such that $v_{j_1} / w_{j_1} < v_i / w_{j_1}$ for all $i in 1...n$ and $i neq j_1$. If we replace $a_{j_1}$ with $a_{n+1}$, the objective function improves by $(v_{n+1} - v_{j_1}) / min(w_{n+1},w_{j_1})$. This is the largest possible increase in the objective function because any other replacement choice subtracts a larger amount than $v_{j_1} / min(w_{n+1},w_{j_1})$. We continue this replacement strategy, choosing $j_k$ as the index of the remaining item with the lowest value-to-weight ratio of the remaining items and replacing it entirely with $w_{j_k}$ of $a_i$ or with as much $a_i$ as remains. When the knapsack is completely full of $a_i$ or all available $a_i$ has been placed in the knapsack, we have an optimal solution, achieved by being as greedy as possible with the choice $a_i$.
QED
$endgroup$
add a comment |
$begingroup$
The proof is by induction.
To pack a fractional knapsack with a single item $a_1$, fill the knapsack to the limit of either the total capacity of the knapsack or the total quantity of $a_1$ available, whichever is less.
Given a fractional knapsack with total weight capacity $W$, and optimally packed with $A = {a_1, a_2, ..., a_n}$, values $V = {v_1, v_2, ..., v_n}$ with weight quantities $W = {w_1, w_2, ..., w_n}$ and a new choice $a_{n+1}$, value $v_{n+1}/w_{n+1} > v_i/w_i$ for all $i in 1...n$ and available weight $w_{n+1}$, then a new optimal solution can be found as follows. Let $j_1$ be the index such that $v_{j_1} / w_{j_1} < v_i / w_{j_1}$ for all $i in 1...n$ and $i neq j_1$. If we replace $a_{j_1}$ with $a_{n+1}$, the objective function improves by $(v_{n+1} - v_{j_1}) / min(w_{n+1},w_{j_1})$. This is the largest possible increase in the objective function because any other replacement choice subtracts a larger amount than $v_{j_1} / min(w_{n+1},w_{j_1})$. We continue this replacement strategy, choosing $j_k$ as the index of the remaining item with the lowest value-to-weight ratio of the remaining items and replacing it entirely with $w_{j_k}$ of $a_i$ or with as much $a_i$ as remains. When the knapsack is completely full of $a_i$ or all available $a_i$ has been placed in the knapsack, we have an optimal solution, achieved by being as greedy as possible with the choice $a_i$.
QED
$endgroup$
The proof is by induction.
To pack a fractional knapsack with a single item $a_1$, fill the knapsack to the limit of either the total capacity of the knapsack or the total quantity of $a_1$ available, whichever is less.
Given a fractional knapsack with total weight capacity $W$, and optimally packed with $A = {a_1, a_2, ..., a_n}$, values $V = {v_1, v_2, ..., v_n}$ with weight quantities $W = {w_1, w_2, ..., w_n}$ and a new choice $a_{n+1}$, value $v_{n+1}/w_{n+1} > v_i/w_i$ for all $i in 1...n$ and available weight $w_{n+1}$, then a new optimal solution can be found as follows. Let $j_1$ be the index such that $v_{j_1} / w_{j_1} < v_i / w_{j_1}$ for all $i in 1...n$ and $i neq j_1$. If we replace $a_{j_1}$ with $a_{n+1}$, the objective function improves by $(v_{n+1} - v_{j_1}) / min(w_{n+1},w_{j_1})$. This is the largest possible increase in the objective function because any other replacement choice subtracts a larger amount than $v_{j_1} / min(w_{n+1},w_{j_1})$. We continue this replacement strategy, choosing $j_k$ as the index of the remaining item with the lowest value-to-weight ratio of the remaining items and replacing it entirely with $w_{j_k}$ of $a_i$ or with as much $a_i$ as remains. When the knapsack is completely full of $a_i$ or all available $a_i$ has been placed in the knapsack, we have an optimal solution, achieved by being as greedy as possible with the choice $a_i$.
QED
answered Aug 19 '15 at 14:46
Michael TiemannMichael Tiemann
337211
337211
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.
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%2f1402668%2fproof-that-the-fractional-knapsack-problem-exhibits-the-greedy-choice-property%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
$begingroup$
You say that item $i$ has the smallest value per weight ratio and $a1$ has the largest. In that case the inequalities are the reverse of what you wrote.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 13:44
$begingroup$
@MichaelTiemann Sorry, for $i$, I meant the item with greatest value per weight ratio (not the smallest) of the original items...
$endgroup$
– nbro
Aug 19 '15 at 13:49
$begingroup$
The proof is not very convincing because (1) it does not explain how all the other choices influence the answer, and (2) it does not treat the specific mathematics of the fractional knapsack problem, namely, that at any given point in the construction of the objective function, an infinitesimal (weight) quantity of a suboptimal choice can be replaced by an equal weight quantity of the greedy choice, until the weight quantity of the greedy choice is exhausted.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:12
$begingroup$
Well, since this problem exhibits optimal substructure, then for your first point my proof should give an answer... not sure if I understood your second point...
$endgroup$
– nbro
Aug 19 '15 at 14:16
$begingroup$
Replacing the previously best choice with the newly best choice is not optimal. You want to replace the previously worst choice with the newly best choice to be optimal, as the following answer shows.
$endgroup$
– Michael Tiemann
Aug 19 '15 at 14:47