Skip to content

Instantly share code, notes, and snippets.

@mtaptich

mtaptich/README.md

Last active March 15, 2016 21:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mtaptich/7c358f687d087e9489bd to your computer and use it in GitHub Desktop.
Save mtaptich/7c358f687d087e9489bd to your computer and use it in GitHub Desktop.
Download ZIP
Knapsack Table
Raw
README.md

A simple example of 0/1 Knapsack Problem Dynamic Programming in d3.js.

Items are first ranked according to weight. Next, at each stage (e.g., item:capacity combination) in the algorithm, the model assesses whether adding a new item (row) improves the solution at that paritcular weight capacity (column). If so, it adds the new item and updates the best solution; otherwise, it obtains the previous best solution. Click the tiles to examine each step.

Once the final solution is found, the model back calculates the optimum item set. Rows with highlighted tiles (blue) correspond to items in this set.

Note: This model purposefully shows only one solution. Can you determine when multiple solutions exist?

Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
width: 1024px;
margin-top: 0;
margin: auto;
font-family: "Lato", "PT Serif", serif;
color: #222222;
padding: 0;
font-weight: 300;
line-height: 33px;
-webkit-font-smoothing: antialiased;
}
text {
pointer-events: none;
}
.tile {
stroke: #000;
stroke-width: 1px;
stroke-dasharray: 4px, 4px;
fill: #ecf0f1;
-webkit-font-smoothing: antialiased;
}
.label{
fill: #fff;
}
.cols, .rows{
fill: #000;
font-size: 32px;
}
.legend{
font-size: 20px;
}
.display{
font-size: 50px;
}
text {
pointer-events: none;
}
.guide{
fill: none;
stroke: red;
stroke-width: 12px;
opacity: 0.3;
-webkit-font-smoothing: antialiased;
}
</style>
<body>
</body>
<script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
<script>
var margin = { 'top': 100, 'right': 20, 'bottom': 150, 'left': 100 },
width = 960 - margin.left - margin.right,
height = 640 - margin.top - margin.bottom,
capacity = Math.floor(Math.random()*5) + 6,
nitems = Math.floor(Math.random()*2) + 4,
sw = width/(capacity+1),
sh = height/(nitems),
translate_speed = 500;
var svg = d3.select('body').append('svg')
.attr('width', width + margin.left + margin.right)
.attr('height', height + margin.top + margin.bottom)
.append('g')
.attr('transform', 'translate(' + margin.left + ',' + margin.top + ')');
var whiteblue = d3.interpolateRgb("#ecf0f1", "#3498db"),
blueorange = d3.interpolateRgb("#3498db", "#f39c12"),
blueblack = d3.interpolateRgb("#3498db", "#000"),
orangeblue = d3.interpolateRgb("#f39c12", "#3498db");
var data = d3.range(nitems).map(function(d){
return d3.range(capacity+1).map(function(e){ return [d,e]})
})
var items = d3.range(nitems).map(function(d,i){
return [Math.ceil(Math.random()*9), Math.ceil(Math.random()*capacity/1.5)] // [value, weight]
})
items = items.sort(function(a,b){ return a[1] - b[1]})
var cols = svg.selectAll('.cols')
.data(d3.range(capacity+1)).enter().append('text')
.attr('class', 'cols')
.attr('transform', function(d,i){
return 'translate('+ ((sw)*i + sw/2 - 5) +','+ (-20) +')'
})
.text(function(d,i){ return i})
.style('text-anchor', 'middle')
svg.append('text')
.text('(val) wt')
.attr('transform', 'translate(' + -50 + ',' + -10 + ')')
.attr('class', 'legend')
.style('text-anchor', 'middle')
var rows = svg.selectAll('.rs')
.data(items).enter().append('text')
.attr('class', function(d, i){ return 'rows r'+i})
.attr('transform', function(d,i){
return 'translate('+ (-50) +','+ (i*(sh+10) + 10 + sh/2) +')'
})
.text(function(d,i){ return '('+d[0]+') '+d[1]})
.style('text-anchor', 'middle')
var display = svg.append('text')
.attr('transform', 'translate(' + (width/2) + ',' + (height+margin.bottom - 30) + ')')
.attr('class', 'display')
.style('text-anchor', 'middle')
.text('...')
var tiles = svg.selectAll('.tiles')
.data(data).enter().append('g')
.selectAll('.tile')
.data(function(d){ return d}).enter()
var rects = tiles.append('rect')
.attr('transform', function(d){ return 'translate('+ ( d[1] * (sw ) ) +','+ ( d[0] * (sh + 10) ) +')' })
.attr('width', sw-10)
.attr('height', sh)
.attr('rx', 3)
.attr('ry', 3)
.attr('class', function(d){ return 'tile _'+d[0]+'_'+d[1]})
.style('fill', '#ecf0f1')
tiles.append('text')
.attr('transform', function(d){ return 'translate('+ ( d[1] * (sw ) ) +','+ ( d[0] * (sh + 10) ) +')' })
.attr('x', sw/2)
.attr('y', sh/2)
.attr('dy', 7)
.attr('dx', -5)
.attr('class', function(d){ return '_'+d[0]+'_'+d[1]+' label'})
.style('text-anchor', 'middle')
.style('font-size', '24');
function disp(t){ display.text(t) }
function up(row, step){
if (row == 0) return 0
d3.select('._'+(row - 1)+'_'+step).transition().duration(translate_speed/2).delay(translate_speed/2)
.attr('rx', 30).attr('ry', 30)
.styleTween("stroke", function() {return orangeblue; })
.transition().duration(translate_speed/2)
.attr('rx', 3).attr('ry', 3)
.styleTween("stroke", function() {return blueblack; });
return d3.select('._'+(row - 1)+'_'+step+'.label').text()
}
function upleft(row, step, wt){
if (row == 0 || step == 0 || step < wt) return 0
d3.select('._'+(row - 1)+'_'+(step-wt)).transition().duration(translate_speed/2).delay(translate_speed/2)
.attr('rx', 30).attr('ry', 30)
.styleTween("stroke", function() {return orangeblue; })
.transition().duration(translate_speed/2)
.attr('rx', 3).attr('ry', 3)
.styleTween("stroke", function() {return blueblack; });
d3.select('.r'+row).transition().duration(translate_speed/2).delay(translate_speed/2)
.style('fill', 'red').transition().duration(translate_speed/2)
.style('fill', '#000');
return d3.select('._'+(row - 1)+'_'+(step-wt)+'.label').text()
}
function txt(row, step, val){
return d3.select('._'+(row)+'_'+step+'.label').transition().duration(translate_speed*1.5).text(val)
}
function intialize(callback){
var st = 0
var setup = setInterval(function(){
if (st <=nitems-1){
d3.select('._'+st+'_0').transition().duration(translate_speed)
.styleTween("fill", function() {return whiteblue; })
.transition().duration(translate_speed)
.styleTween("fill", function() {return blueorange; });
txt(st,0, 0)
st++
} else{
clearInterval(setup);
callback()
}
}, 200)
}
function on_complete(d,i){
var u = up(d[0],d[1]);
var ul = +upleft(d[0],d[1],items[d[0]][1]);
if (d[1] >= items[d[0]][1]){ disp(u+' or '+(items[d[0]][0] + ul)+' ('+items[d[0]][0]+' + '+ul+')')}
else{ disp(u)}
upleft(d[0], i, items[d[0]][1])
}
function knapsack(current_row){
var st = 1, it = current_row;
var setup = setInterval(function(){
if (st <=capacity){
// color tiles
d3.select('._'+it+'_'+st).transition().duration(translate_speed)
.styleTween("fill", function() {return whiteblue; })
.transition().duration(translate_speed)
.styleTween("fill", function() {return blueorange; });
if (st < items[it][1]){
var u = up(it,st);
disp(u)
txt(it,st,u)
} else{
var u = up(it,st);
var ul = +upleft(it,st,items[it][1]);
disp(u+' or '+(items[it][0] + ul)+' ('+items[it][0]+' + '+ul+')')
txt(it, st, u > items[it][0] + ul ? u : items[it][0] + ul)
}
st++
} else{
clearInterval(setup);
if (current_row < nitems -1){
return knapsack(current_row+1)
} else{
translate_speed *=2;
var prev_color
rects.on('mouseover', function(){
prev_color = d3.select(this).style('fill')
d3.select(this).style('fill', '#f1c40f')
})
rects.on('mouseout', function(){ d3.select(this).style('fill', prev_color)})
rects.on('click', on_complete)
var coors = getItems(nitems-1, capacity, [])
line(coors)
return null
}
}
}, translate_speed)
}
function getItems(r,c,d){
if (r==0 || c==0){
d.push([r,c]);
return d
}
var o = d3.select('._'+(r)+'_'+(c)+'.label').text(),
u = d3.select('._'+(r-1)+'_'+(c)+'.label').text(),
l = d3.select('._'+(r)+'_'+(c-1)+'.label').text();
if (o==u) {
return getItems(r-1,c, d)
}else if (o==l){
return getItems(r,c-1, d)
}else{
d.push([r,c]);
return getItems(r-1, c-items[r][1],d)
}
}
function line(coors){
var pos = d3.select('._'+(nitems-1)+'_'+(capacity))
.attr('transform').replace('translate(','').replace(')','').split(',');
var start = (+pos[0]+sw/2)+','+(+pos[1]+sh/2),
p = '',
o = 0;
var prev = [nitems-1, capacity];
for (var i = 0; i < coors.length; i++) {
var _c = coors[i],
ts = i ==0 ? 0 : 1
a = (sh+10)*(prev[0] - coors[i][0]) - 5*(ts),
b = sw*(prev[1] - coors[i][1]) + 5*(ts),
prev = _c;
d3.select('._'+_c[0]+'_'+_c[1]).transition().duration(translate_speed)
.styleTween("fill", function() {return whiteblue; })
p+='v-'+a+'h-'+b
o+= a+b
};
svg.append('path')
.attr('class', 'guide')
.attr('d', 'M'+start+p)
.style('stroke-dasharray', o+' '+o)
.attr('stroke-dashoffset', o)
.attr('stroke-linejoin', 'round')
.transition()
.duration(1500)
.attr('stroke-dashoffset', 0)
}
intialize(function(){
knapsack(0);
})
d3.select(self.frameElement).style("height", 640 + "px");
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment