/* 応用情報技術者試験平成29年秋期午後問3 アルゴリズム */ var size = [1, 2, 3]; var value = [2, 6, 9]; var N = size.length; //品物の数 var maxvalue = new Array(N); var choice = new Array(N); var V = 5; document.write('<table border="1" style="border-collapse:collapse;"><tr><th>容量制限'); for (var k=0; k<=V; k++) { maxvalue[k] = 0; choice[k] = -1; document.write('<th>'+k); } for (var s=0; s<=N-1; s++) { document.write('<tr><td>'+s+'までを選べる'); document.write('<td>-'.repeat(s+1)); for (var t=size[s]; t<=V; t++) { temp = maxvalue[t-size[s]] + value[s]; if (temp > maxvalue[t]) { maxvalue[t] = temp; choice[t] = s; } document.write('<td>'+maxvalue[t]); } } document.write('</table>選んだ品物=>'); k = V; while (choice[k] >= 0) { document.write(choice[k]+','); k = k - size[choice[k]]; } document.write('<br>容量制限'+V+'における価値合計は'+maxvalue[V]);