0-1 Knapsack Problem

From Algorithmist
Jump to navigation Jump to search

See http://en.wikipedia.org/wiki/Knapsack_problem

Algorithm[edit]

if(w< wt[i])
 {
    V[i][w]=V[i-1][w];
 }
 else
 {
     V[i][w]=max(V[i-1][w],val[i]+V[i-1][w-wt[i]]);
 }

Implementation[edit]

See http://www.shawonruet.com/2016/04/uva-10130-supersale.html