再帰についてです

[初心者]

何枚かの切手があるときに, 切手の金額の合計がちょうど与えられた金額になる組合せを求めるプログラムを作成する. このプログラムはまず目標の金額を入力した後, 切手１の金額と最大枚数, 切手２の金額と最大枚数, ... , 切手ｎの金額と最大枚数を入力する. 切手の金額として0 を入力すると終了とする. その後, 入力した切手の金額と最大枚数の範囲内で目標金額と等しくなる組合せを１つ出力する

この問題なんですけど再帰でのやり方が思いつきません。どなたかヒントをくれないでしょうか？

[box]

本題にいく前に、前提条件を整理しておきます。
切手は何種類ありますか？
切手の金額と最大枚数の積和が、そもそも希望金額に達しない場合、どうしますか？
切手の金額と最大枚数の積和は希望金額以上であるが、ちょうど希望金額になる組み合わせがない場合、
どうしますか？

[初心者]

１、切手の種類は自分で決められます。
２、達しない場合解なしとします。
３、その場合は解なしとします。
ちょうど希望金額の同じになった時だけその組み合わせを出力したいのです。

私的にはｎ重ループを再帰で書き換えると思うのですがわかりません。

[box]

> ｎ重ループを再帰で書き換える

では、手始めにn重ループで実装してみてはいかがでしょうか。
実装したコードをながめているうちに、ループから再帰へ
どう変化させればよいかが見えてくるかもしれません。

[初心者]

すいません
ずっと考えているのですが、どうにもアルゴリズムがおもいつきません（泣

[lbfuvab]

全て1枚は買うなどの条件はありますか？
それとも0枚でもいいのですか？

[初心者]

0枚でもよいです。

[box]

具体的な例題から一般化するとよいかもしれません。例えば、
1円切手9枚、10円切手8枚、100円切手7枚があるとします。
合計が543円になる組み合わせは、何でしょうか。また、
その組み合わせを手で求める際、どういう手順を踏んだでしょうか。

[初心者]

1円切手３枚、10円切手４枚、100円切手５枚ですね
大きいほうから決めていきました。

[box]

その手順を、プログラムにしてみてください。

[初心者]

for
金額を超えないまでたす。
if(まだ足せそうだったらn-1で再帰)
else if(あったら出力)
else if(超えてしまったら最初からやり直し)
こんな感じだと思うのですが分かりません

[lbfuvab]

再帰についてですが

int saiki(int depth,int NowMoney);//depthは呼び出しの深さ(0から始まりn-1が最終) NowMoneyは呼び出された時点での合計額

でいけると思いますよ。

関数内での処理は
(SUCCESS,FAILUREは定数でNumStanpは枚数を保存する配列)
①　depthがnを超えたら失敗(return FAILURE;)
②　枚数を1枚ずつ増やしていき・・・
③a 合計額が目標金額を超えたら失敗。(return FAILURE;)
③b 合計額が目標金額と同じなら成功。その時の枚数をNumStanp[depth]に登録
③c 合計額が目標金額より少ないならもう一度saikiを呼び、SUCCESSが帰ってきたら枚数をNumStanp[depth]に保存。

でいけると思います。

[初心者]

一度考えてきます。
またわからなくなったらよろしくお願いします。

[初心者]

これって深さ優先探索ですよね？
おおまかにプログラムを書いてくれませんか？

[初心者]

これですべての組み合わせを考えることが出来るのでしょうか？

[初心者]

#include<stdio.h>
void kitte(int , int,int );
int sum, s[100]={0}, k[100]={0};
int main(void)
{
	int i=0,gk=0;
	fprintf(stderr,"合計金額>>>");
	scanf("%d", &sum);
	while(1)
		{
			fprintf(stderr,"切手の金額と最大枚数を入力せよ>>>");
			scanf("%d %d",&s,&k);
			if(k==0)
				{
					break;
				}
			i++;
		}
	kitte(i+1,0,gk);

return 0;
}

void kitte(int c,int d ,int gk)
{
		
		int i,j;
		int h[100]={0};
	if(c<=d)
		{
			printf("NO\n");
		}
	else	{
			for(i=0;i<=k[d];i++)
				{
					gk+=i*s[d];
				
					if(sum-gk<0)
						{
							gk-=i*s[d];
						}
					else if(sum-gk==0)
						{
							h[d]=i;
							for(j=0;j<c;j++)
								{
									printf("%d切手%d枚\n",s[j],h[j]);
								}
						}
					else
						{
							kitte(c,d+1,gk);
							h[d]=i;
							gk-=i*s[d];
						}
				}
		}

}

ここから分かりません

[初心者]

出来ました