Zero-One KnapSack146 views

AlgoPill 
 function knapSack(v,w,c){
    var mat=[],take=[],i,j,ret=[],tmp;

    for(i=0;i<=c;i++){ // for every knapsack size
        mat.push([]); take.push([]);
        for(j=0;j<=v.length;j++){ // for each number of elements
            if(i===0||j===0){
                mat[i][j]=0;
            } else {
                mat[i][j]=mat[i][j-1];
                // only if we have enough space in current size of knapsack
                if(w[j-1]<=i){
                    tmp=v[j-1]+mat[i-w[j-1]][j-1];
                    // max of taking j-th element and not taking it
                    if(tmp>mat[i][j-1]){
                        mat[i][j]=tmp;
                        take[i][j]=true;
                    } 
                } 
            }
        }
    }
    // construct solution
    for(i=v.length;i>0;i--){
        if(take[c][i]){
            ret.push(i-1); 
            c = c - w[i-1];
        } 
    }
    return ret.reverse();

}

Problem Statement: Given list (v) of values and (w) of weights and a capacity (c) of knapsack, find out elements that should be selected from the input list such that total value is maximum subject to the condition that total weight cannot be more than the capacity c of the  knapsack.

Solution: 0/1 knapsack is a standard optimization problem. we use a dynamic programming solution for the problem. The solution starts by solving the smaller problems and building up to the final solution. In order to solve this problem we need to solve O(c*n) smaller problems. We solve the smallest problem first and then the next and so on. Each of these snaller problems can be solved in constant amount of time, therefore the time complexity of overall solution is O(c*n)

given a knapsack c’ such that 0<= c’ <=c and a number n’ of object such that 1<=n’<=n

max_posible_value(n’,c’) = max(v[n']+max_possible_value(n’-1,c’-w[n'],max_possible_value(n’-1,c’));

that is, maximum of  {[ value of selecting current element n'+ the max value possible with n'-1 element and sack of capacity c'-w[n']] and value of not selecting current element and thus max value with n’-1 elements and sack of capcity c’}

In addition to finding these solutions of sub problems we also keep track of whether current element n’ was selected or not for the current  sack of size c’, this helps us in constructing the list of objects that should be selected for maximum value.

Post a Comment

You must be logged in to post a comment.