下記のプログラムは、
- sum
sum
円の所持金があり、nn
種類の商品の中からcntcnt
個の商品を選びお釣り(minmin
円)を最小にする
というアルゴリズムです(商品は安い順にx[1]x[1]
円,x[2]x[2]
円,,,,x[n]x[n]
円と示されます)
現状ではそれぞれcnt、下記のコードのとおり、回文の中に依存し回文といった構造になっており、cnt
の値によってループの式数やループの条件が変わっていくようになっていおりますが。
cnt
の値は入力値で与えられるため、cntに依存しないようどのcnt
の値にも対応可能な統合式にするためにはを作りたいのですが、どのようにすればいいのでしょうか?
// cnt=2の場合
int min=10000001;
for(int k=n;sum>=x[k]&&k>=cnt;k--){
for(int j=k-1;sum>=x[k]+x[j]&&j>=cnt-1;j--){
min=min>(sum-x[k]-x[j])?(sum-x[k]-x[j]):min;
}
}
または、と
// cnt=4の場合
int min=10000001;
for(int k=n;sum>=x[k]&&k>=cnt;k--){
for(int j=k-1;sum>=x[k]+x[j]&&j>=cnt-1;j--){
for(int i=j-1;sum>=x[k]+x[j]+x[i]&&i>=cnt-2;i--){
for(int l=i-1;sum>=x[k]+x[j]+x[i]+x[l]&&l>=cnt-3;l--){
min=min>(sum-x[k]-x[j]-x[i]-x[l])?(sum-x[k]-x[j]-x[i]-x[l]):min;
}
}
}
}
✳︎初心者であるため、適切でない表現が含まれていますがご了承ください