JSFiddle - React, Tailwind, and code Playground

by eelyafi

HTML

<ul id='lst' style="list-style:none;"></ul>

JavaScript

$(function(){
    //K(w) = Max(K[w-wi]+vi) constraint i:wi<=w
    function knapsack_repedition(W, items, prev){
        var K = new Array(W);
        $.each(K, function(i, e){
            K[i] = 0
        })
        for (w = 1; w <= W; w++) {
            var maxval = 0;
            $.each(items, function(k, v){
                var wi = v.Weight;
                var vi = v.Value;
                if (wi <= w) {
                    val = K[w - wi] + vi
                    if (val > maxval) {
                        maxval = val;
                        //for this w, we choose item i that maximizes K[w-wi]+vi
                        prev[w] = v
                    }
                }
            })
            K[w] = maxval
        }
        return K[W]
    }
 
    function getSelectedItems(n, prev){
        if (n == 0)
            return new Array();
        var arr = getSelectedItems((n - prev[n].Weight), prev);
        arr.push(prev[n])
        return arr;
    }
 
    var items = {
        item1: {
            Weight: 6,
            Value: 30
        },
        item2: {
            Weight: 3,
            Value: 14
        },
        item3: {
            Weight: 4,
            Value: 16
        },
        item4: {
            Weight: 2,
            Value: 9
        },
        item5: {
            Weight: 5,
            Value: 24
        }
    }
 
    //
    var W = 10;
    var prev = {}
    var Kmax = knapsack_repedition(W, items, prev)
    var Kselected = getSelectedItems(W, prev)
 
    log('Max Value = ' + Kmax)
    $.each(Kselected, function(i, e){
        log(i + ' : ' + e.Weight)
    })
 
    function log(msg){
        $('#lst').append('<li>' + msg + '</li>')
    }
});