内容

ナップサック問題を解きます。

シェル芸

echo | awk '{m=0;for(a=0;a<14;a++){for(b=0;b<19;b++){for(c=0;c<12;c++){for(d=0;d<24;d++){for(e=0;e<11;e++){if(a*15+b*11+c*18+d*8+e*21<=185&&a*121+b*86+c*162+d*68+e*187>m){m=a*121+b*86+c*162+d*68+e*187}}}}}};print m}'

解説

実は全探索で解けます。動的計画法を使う方法も考えてみましょう。

ウェブサイト

シェル芸オンラインジャッジ : https://shellgei-online-judge.com/