再帰関数で最小になる組み合わせを求めたい

Question

500円玉を持っていて5種類の中からお菓子を買うときの最小となるおつりの組み合わせを全て求めたいのですが再帰の部分でうまく作れず悩んでいます。
再帰を行ったときにコード上のjとquaの値を変更するようにしたいです。

何か良い方法ありましたらご教示願いたいです。

    let N = 5;
    let X = 500;
    let array = [300, 170, 120, 70 , 30]
　　let j = 0;
    function Calc(money,qua,val){
 //       console.log(money)
        if(qua == 0){
            res = money;
        } else if(money > val[j]){
            rmoney = money - val[j];
            j = j+1;
            qua = qua - 1;
            res = Math.min(Calc(rmoney,qua,val),
                  Calc(money,qua,val));
        } else{
            j = j+1;
            qua = qua - 1;
            Calc(money,qua,val);
        }
        return res;
    }
    
    console.log(Calc(X,N,array));

Comments

[m.ts10806]

>javasript
JavaScriptです。
ただ、タグにあるので書く必要はないですが

[yambejp]

「最小のおつりを求めたい」だと0になった瞬間に計算終了ですけど・・・
「最小のおつりになる組み合わせを全て求めたい」じゃなくてよいですか？

いじわるな言い方をすれば、「500円を持って」も設問としては不合格
500円玉（500円札？）じゃなければあまり意味がないです。
500円が最初から崩れた状態であれば「おつりは常に0円」です

[m.ts10806]

>javasript
JavaScriptです。
ただ、タグにあるので書く必要はないですが

[ryoma_]

すいません。タイトルと問題文の方を修正しました。

Answer 1

こんにちは。

Calc関数にjを渡せばいいのではないでしょうか？

    let N = 5;
    let X = 500;
    let array = [300, 170, 120, 70 , 30]
    function Calc(money,qua,val,j){
        if(qua == 0) return money;
        if(money > val[j]){
            let rmoney = money - val[j];
            return Math.min(Calc(rmoney, qua-1, val, j+1),
                  Calc(money, qua-1, val, j+1));
        }
        return Calc(money, qua-1, val, j+1);
    }

    console.log(Calc(X,N,array,0));

Comments

[ryoma_]

ご回答ありがとうございます。Calcにｊを渡すことで無事動かすことが出来ました。
ありがとうございます！

Answer 2

このくらいなら組み合わせ可能な全通りをとって、最小値でフィルタすればよいのでは？

Comments

[yambejp]

<div id="v"></div>
<script>
const v=document.querySelector('#v');
const X=500;
const fill=(x,y)=>Array(Math.floor(y/x)+1).fill(null).map((y,z)=>Array(z).fill(x));
const combi=(a1,a2)=>a1.reduce((x,y)=>(x.push(...a2.map(z=>[y,z])),x),[]).map(x=>x.flat());

const a=[300, 170, 120, 70 , 30];
const b=a.reduce((x,y)=>combi(x,fill(y,X)),[[]]).filter(x=>x.length>0 && x.reduce((y,z)=>y+z)<=X);
const min=Math.min(...b.map(x=>X-x.reduce((y,z)=>y+z)));
b.filter(x=>X-x.reduce((y,z)=>y+z)==min).forEach(x=>v.innerHTML+=x.join(",")+"<br>");
</script>

[yambejp]

参考までに

https://codepen.io/yambejp/pen/xxRZLwe

[ryoma_]

ご回答ありがとうございます。確かに全通りをとっても良いですね。codepenの方もありがとうございます。