|
<!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> |