Proof that the fractional knapsack problem exhibits the greedy-choice property












1












$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?










share|cite|improve this question











$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
















1












$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?










share|cite|improve this question











$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














1












1








1


3



$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?










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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


















  • $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










1 Answer
1






active

oldest

votes


















0












$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






share|cite|improve this answer









$endgroup$














    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
    });


    }
    });














    draft saved

    draft discarded


















    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









    0












    $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






    share|cite|improve this answer









    $endgroup$


















      0












      $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






      share|cite|improve this answer









      $endgroup$
















        0












        0








        0





        $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






        share|cite|improve this answer









        $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







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Aug 19 '15 at 14:46









        Michael TiemannMichael Tiemann

        337211




        337211






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            Bundesstraße 106

            Verónica Boquete

            Ida-Boy-Ed-Garten