0/1 배낭 문제

<canvas id="stage"></canvas><div class="controls"><button id="restart" type="button">처음부터</button><button id="step" type="button">한 단계</button><label>속도 <input id="speed" type="range" min="1" max="5" value="3"></label></div>

body{display:block}#stage{position:absolute;inset:0;width:100%;height:100%}.controls{position:absolute;bottom:9px;left:50%;transform:translateX(-50%);display:flex;align-items:center;gap:7px;white-space:nowrap}.controls button,.controls label{font:12px sans-serif;color:var(--fg);background:var(--surface);border:1px solid var(--line);border-radius:6px;padding:5px 8px}.controls button{cursor:pointer}.controls input{width:75px;vertical-align:middle;accent-color:var(--accent)}@media(max-width:500px){.controls{display:none}}

const frames = [{"kind":"table","caption":"물건 0개 · 가치 0","data":{"values":[[0,0,0,0,0,0,0],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"]}},{"kind":"table","caption":"1번 물건 · 용량 0 → 최대 0","data":{"values":[[0,0,0,0,0,0,0],[0,"·","·","·","·","·","·"],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[1,0],"sources":[[0,0]]}},{"kind":"table","caption":"1번 물건 · 용량 1 → 최대 0","data":{"values":[[0,0,0,0,0,0,0],[0,0,"·","·","·","·","·"],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[1,1],"sources":[[0,1]]}},{"kind":"table","caption":"1번 물건 · 용량 2 → 최대 3","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,"·","·","·","·"],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[1,2],"sources":[[0,2],[0,0]]}},{"kind":"table","caption":"1번 물건 · 용량 3 → 최대 3","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,"·","·","·"],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[1,3],"sources":[[0,3],[0,1]]}},{"kind":"table","caption":"1번 물건 · 용량 4 → 최대 3","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,"·","·"],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[1,4],"sources":[[0,4],[0,2]]}},{"kind":"table","caption":"1번 물건 · 용량 5 → 최대 3","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,"·"],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[1,5],"sources":[[0,5],[0,3]]}},{"kind":"table","caption":"1번 물건 · 용량 6 → 최대 3","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],["·","·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[1,6],"sources":[[0,6],[0,4]]}},{"kind":"table","caption":"2번 물건 · 용량 0 → 최대 0","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,"·","·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[2,0],"sources":[[1,0]]}},{"kind":"table","caption":"2번 물건 · 용량 1 → 최대 0","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,"·","·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[2,1],"sources":[[1,1]]}},{"kind":"table","caption":"2번 물건 · 용량 2 → 최대 3","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,"·","·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[2,2],"sources":[[1,2]]}},{"kind":"table","caption":"2번 물건 · 용량 3 → 최대 4","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,"·","·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[2,3],"sources":[[1,3],[1,0]]}},{"kind":"table","caption":"2번 물건 · 용량 4 → 최대 4","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,"·","·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[2,4],"sources":[[1,4],[1,1]]}},{"kind":"table","caption":"2번 물건 · 용량 5 → 최대 7","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,"·"],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[2,5],"sources":[[1,5],[1,2]]}},{"kind":"table","caption":"2번 물건 · 용량 6 → 최대 7","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,7],["·","·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[2,6],"sources":[[1,6],[1,3]]}},{"kind":"table","caption":"3번 물건 · 용량 0 → 최대 0","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,7],[0,"·","·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[3,0],"sources":[[2,0]]}},{"kind":"table","caption":"3번 물건 · 용량 1 → 최대 0","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,7],[0,0,"·","·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[3,1],"sources":[[2,1]]}},{"kind":"table","caption":"3번 물건 · 용량 2 → 최대 3","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,7],[0,0,3,"·","·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[3,2],"sources":[[2,2]]}},{"kind":"table","caption":"3번 물건 · 용량 3 → 최대 4","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,7],[0,0,3,4,"·","·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[3,3],"sources":[[2,3]]}},{"kind":"table","caption":"3번 물건 · 용량 4 → 최대 5","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,7],[0,0,3,4,5,"·","·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[3,4],"sources":[[2,4],[2,0]]}},{"kind":"table","caption":"3번 물건 · 용량 5 → 최대 7","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,7],[0,0,3,4,5,7,"·"]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[3,5],"sources":[[2,5],[2,1]]}},{"kind":"table","caption":"3번 물건 · 용량 6 → 최대 8","data":{"values":[[0,0,0,0,0,0,0],[0,0,3,3,3,3,3],[0,0,3,4,4,7,7],[0,0,3,4,5,7,8]],"rowLabels":["0","2/3","3/4","4/5"],"colLabels":["0","1","2","3","4","5","6"],"active":[3,6],"sources":[[2,6],[2,2]]}}];
const title = "배낭 문제 · 넣기/빼기";
const canvas = document.getElementById('stage');
const ctx = canvas.getContext('2d');
const restart = document.getElementById('restart');
const step = document.getElementById('step');
const speed = document.getElementById('speed');
let index = 0, last = performance.now(), width = 300, height = 200;
function colors(){ const s=getComputedStyle(document.documentElement); const v=(key)=>s.getPropertyValue(key).trim(); return {bg:v('--bg'),fg:v('--fg'),muted:v('--muted'),line:v('--line'),surface:v('--surface'),accent:v('--accent'),accent2:v('--accent-2'),accent3:v('--accent-3')}; }
function resize(){ const dpr=Math.min(devicePixelRatio||1,2); width=innerWidth;height=innerHeight;canvas.width=Math.round(width*dpr);canvas.height=Math.round(height*dpr);ctx.setTransform(dpr,0,0,dpr,0,0);draw(); }
function text(value,x,y,color,size=12,align='left'){ ctx.fillStyle=color;ctx.font='600 '+size+'px sans-serif';ctx.textAlign=align;ctx.textBaseline='middle';ctx.fillText(String(value),x,y); }
function line(x1,y1,x2,y2,color,thick=2){ctx.strokeStyle=color;ctx.lineWidth=thick;ctx.beginPath();ctx.moveTo(x1,y1);ctx.lineTo(x2,y2);ctx.stroke();}
function dot(x,y,r,color){ctx.fillStyle=color;ctx.beginPath();ctx.arc(x,y,r,0,Math.PI*2);ctx.fill();}
function draw(){
  if(!frames.length)return;
  const p=colors(), frame=frames[index], d=frame.data, detail=width>500;
  ctx.fillStyle=p.bg;ctx.fillRect(0,0,width,height);
  text(title,12,18,p.fg,detail?16:13);text(frame.caption,12,detail?43:39,p.muted,detail?13:10);
  text((index+1)+' / '+frames.length,width-12,18,p.muted,10,'right');
  const top=detail?62:53, bottom=detail?height-47:height-9, span=Math.max(10,bottom-top), areaW=Math.min(width-22,detail?710:width-22), left=(width-areaW)/2;
  if(frame.kind==='graph'){
    const nodes=d.nodes, edges=d.edges, positions=Object.fromEntries(nodes.map(n=>[n.id,{x:left+areaW*(.06+.88*n.x),y:top+span*(.11+.78*n.y)}]));
    for(const edge of edges){const a=edge[0],b=edge[1],weight=edge[2],key=[a,b].sort().join('-'),pa=positions[a],pb=positions[b];
      if(d.hideUnvisited&&(!d.visited.includes(a)||!d.visited.includes(b)))continue;
      const chosen=d.selected?.includes(key), active=d.activeEdge===key;ctx.globalAlpha=active||chosen?1:.58;line(pa.x,pa.y,pb.x,pb.y,active?p.accent2:chosen?p.accent:p.muted,active?4:chosen?3:2);ctx.globalAlpha=1;
      if(d.directed){const angle=Math.atan2(pb.y-pa.y,pb.x-pa.x),x=pb.x-Math.cos(angle)*(detail?18:13),y=pb.y-Math.sin(angle)*(detail?18:13);line(x-Math.cos(angle-.55)*7,y-Math.sin(angle-.55)*7,x,y,p.muted,1.5);line(x-Math.cos(angle+.55)*7,y-Math.sin(angle+.55)*7,x,y,p.muted,1.5);}
      if(weight>0&&!d.hideUnvisited)text(weight,(pa.x+pb.x)/2,(pa.y+pb.y)/2-7,p.muted,10,'center');
    }
    for(const node of nodes){if(d.hideUnvisited&&!d.visited.includes(node.id))continue;const pt=positions[node.id],selected=d.visited?.includes(node.id),front=d.frontier?.includes(node.id),active=d.active===node.id;let color=active?p.accent2:front?p.accent3:selected?p.accent:p.surface;
      if(d.groups){const group=d.groups[nodes.findIndex(n=>n.id===node.id)];color=[p.accent,p.accent2,p.accent3][nodes.findIndex(n=>n.id===group)%3];}
      dot(pt.x,pt.y,detail?18:12,color);ctx.strokeStyle=p.line;ctx.lineWidth=1;ctx.stroke();text(node.id,pt.x,pt.y,selected||active||front||d.groups?'#fff':p.fg,detail?13:10,'center');
      if(d.distances)text(Number.isFinite(d.distances[node.id])?d.distances[node.id]:'∞',pt.x,pt.y+(detail?29:22),p.muted,10,'center');
    }
  } else if(frame.kind==='grid'||frame.kind==='table'||frame.kind==='bits'){
    const table=frame.kind==='table',bits=frame.kind==='bits';const rows=bits?1:table?d.values.length:d.rows,cols=bits?d.bits.length:table?d.values[0].length:d.cols;
    const labelX=table?24:0,labelY=table?18:0,cell=Math.min((areaW-labelX)/cols,(span-labelY)/rows,detail?56:32),ox=left+(areaW-(cols*cell+labelX))/2+labelX,oy=top+(span-(rows*cell+labelY))/2+labelY;
    if(table){d.colLabels.forEach((label,c)=>text(label,ox+c*cell+cell/2,oy-10,p.muted,10,'center'));d.rowLabels.forEach((label,r)=>text(label,ox-12,oy+r*cell+cell/2,p.muted,10,'center'));}
    for(let r=0;r<rows;r++)for(let c=0;c<cols;c++){const n=r*cols+c,x=ox+c*cell,y=oy+r*cell,active=bits?d.active?.includes(c):table?d.active?.[0]===r&&d.active?.[1]===c:d.active===n,source=table?d.sources?.some(v=>v[0]===r&&v[1]===c):false,visited=bits?d.bits[c]:table?false:d.visited?.includes(n),front=d.frontier?.includes(n),blocked=d.blocked?.includes(n),path=d.path?.includes(n),queen=d.queens?.[r]===c;
      ctx.fillStyle=blocked?p.line:active?p.accent2:path||queen?p.accent3:front?p.accent2:visited?p.accent:source?p.accent3:bits&&d.bits[c]?p.accent:p.surface;ctx.fillRect(x+2,y+2,cell-4,cell-4);ctx.strokeStyle=p.muted;ctx.globalAlpha=.42;ctx.strokeRect(x+1,y+1,cell-2,cell-2);ctx.globalAlpha=1;
      const value=bits?d.bits[c]:table?d.values[r][c]:queen?'Q':d.start===n?'S':d.goal===n?'G':blocked?'':visited?'·':'';
      if(value!==''&&value!==undefined)text(value,x+cell/2,y+cell/2,(active||path||queen||front||visited||bits&&d.bits[c])?'#fff':p.fg,Math.min(13,cell*.43),'center');
      if(bits)text(c,x+cell/2,y+cell+11,p.muted,9,'center');
    }
  } else if(frame.kind==='intervals'){
    const rowH=Math.min(31,span/d.intervals.length),unit=(areaW-28)/10,ox=left+10,oy=top+(span-rowH*d.intervals.length)/2;
    d.intervals.forEach((it,i)=>{const y=oy+i*rowH;ctx.fillStyle=d.active===i?p.accent2:d.selected.includes(i)?p.accent:p.line;ctx.fillRect(ox+it[0]*unit,y+3,Math.max(5,(it[1]-it[0])*unit-3),rowH-7);text(i+1,ox-5,y+rowH/2,p.muted,10,'right');});
  } else if(frame.kind==='ring'){
    const cx=width/2,cy=top+span/2,r=Math.min(areaW,span)*.35,loc=(v,rr)=>({x:cx+Math.sin(v*2*Math.PI)*rr,y:cy-Math.cos(v*2*Math.PI)*rr});ctx.strokeStyle=p.muted;ctx.globalAlpha=.6;ctx.lineWidth=2;ctx.beginPath();ctx.arc(cx,cy,r,0,Math.PI*2);ctx.stroke();ctx.globalAlpha=1;
    d.keys.forEach((key,i)=>{const point=loc(key,r),server=d.servers.find(s=>s.id===d.owners[i]),dest=loc(server.pos,r);line(point.x,point.y,dest.x,dest.y,d.active===i?p.accent2:p.line,1);dot(point.x,point.y,d.active===i?6:4,d.active===i?p.accent2:p.fg);});
    d.servers.forEach((server,i)=>{const point=loc(server.pos,r);dot(point.x,point.y,detail?15:11,[p.accent,p.accent2,p.accent3,p.fg][i]);text(server.id,point.x,point.y,i===3?p.bg:'#fff',11,'center');});
  } else if(frame.kind==='points'){
    const side=Math.min(areaW,span)-8,ox=(width-side)/2,oy=top+(span-side)/2;ctx.strokeStyle=p.muted;ctx.globalAlpha=.5;ctx.strokeRect(ox,oy,side,side);ctx.globalAlpha=1;ctx.beginPath();ctx.arc(ox,oy+side,side,Math.PI*1.5,0);ctx.strokeStyle=p.muted;ctx.stroke();
    d.points.forEach(([x,y])=>dot(ox+x*side,oy+side-y*side,detail?2.5:1.7,x*x+y*y<=1?p.accent:p.accent2));
  }
}
function advance(){index=(index+1)%frames.length;draw();}
restart.addEventListener('click',()=>{index=0;last=performance.now();draw();});
step.addEventListener('click',()=>{advance();last=performance.now();});
addEventListener('resize',resize);resize();
function loop(now){const delay=900-Number(speed.value)*140;if(now-last>delay){advance();last=now;}requestAnimationFrame(loop);}requestAnimationFrame(loop);