組み合わせ？のプログラムの考え方が分かりません！！

[チャイナ]

課題について自分で考えてみたのですが、分からなかったため教えていただきたいです。

問)10mの長さの棒から{5m、4m、3m、2m}の棒を切り取るときの組み合わせを答えよ。

組み合わせが、{5}、{5、4}、{5、3}、{5、3、2}、・・・って感じです。2次元配列にしたいのですがfor文を使ってみてもどうすればいいか分からなくなってしまいました。

皆さんの考え方をぜひ教えていただきたいです！

[usao]

組み合わせの全パターンの数だけループして，各パターンについて合計が10mを超えないか否かを調べてやればいいよね．
↓
４種類の棒の 有る/無し の組み合わせは16パターンで，「全て無し」パターンについては調べるまでもないから，単純に残りの 15 種類分だけ回るループを書けばいいよ．

コード:

for( int i=1; i<=15; ++i )
{ /*i番目のパターンについて調べて可であれば表示する*/ }

[usao]

各棒の 有る/無し は，上記の i の値の bitパターン から得れば良いと思う．

…っていう話が「ちょっと何言ってるかわかんないですね」とかいう場合であっても，
せいぜい 15 パターンしかないのだから，好きなように全部のパターンをハードコーディングしてやってもいいと思う．

[チャイナ]

ご返信ありがとうございます！

なるほど。15種類ループですね。

問題なのですが、組み合わせは同じのを何回も使っていい、という条件です。明記し忘れました！すみません。

[usao]

> 組み合わせが、{5}、{5、4}、{5、3}、{5、3、2}、・・・

っていう記述から，それを読み取るのは難易度高いｗ

つーことは，{5,5} っていうパターンも有りだと．
そしたら 15 パターンとかいう話では無くなるし，力業の全探索みたいなのはやりたくない気がする．

[みけCAT]

再帰で、
・今考えている長さを切り出し、また同じ長さについて考える
・今考えている長さは切り出さず、次の長さについて考える
をするといいと思います。

Python で実装してみました。

コード:

def compute(sourceLength, targetLengthList):
	ans = []
	# 全ての切り取る長さの候補を試し終わった
	if len(targetLengthList) == 0:
		return [[]]
	# 今の切り取る長さの候補を試す
	if targetLengthList[0] <= sourceLength:
		# この長さを切り取った後のパターンを生成する
		putterns = compute(sourceLength - targetLengthList[0], targetLengthList)
		# 生成したパターンに、この長さを切り取るという情報を加える
		ans += [[targetLengthList[0]] + puttern for puttern in putterns]
	# 次の切り取る長さの候補に移る
	ans += compute(sourceLength, targetLengthList[1:])
	# 結果を返す
	return ans

print(compute(10, [5, 4, 3, 2]))

[usao]

まぁ，ふつーに(?)，
・5を0個切り出す世界
・5を1個切り出す世界
・5を2個切り出す世界
のそれぞれについて，「残りの長さについて 4,3,2 の組み合わせを列挙」という，元の長さと棒の種類が小さくなった問題を解く，という話にしていくのが素直かな．
（言うまでもないが，そこでも，4をX個切り出す世界のそれぞれについて「残りの長さについて 3,2 の組み合わせを列挙」というさらなる小さい問題にしていく感じ．）

C言語なら再帰で書くのが楽かな．
（って書いてたら話が被ったようだが，せっかくだから送信しちゃうぜ）

[dic]

{5,5}や最大で{2,2,2,2,2}がありなら
再帰でとくのがいいと思います。
深さが５までで、10m以内になるように呼び出していけばできると思います。

ソースは・・・おやすみなさい。

オイラもかぶった

[あたっしゅ]

東上☆海美☆「

コード:

//
// https://dixq.net/forum/viewtopic.php?f=3&t=21547
// 組み合わせ？のプログラムの考え方が分かりません！！ - ミクプラ(ja)
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


const int BUFMAX = 5 * 2 + 1;
char buf[ BUFMAX ];

void
clearBuf()
{
	memset( buf, 0, BUFMAX );
}


int
calc(int sum, char* pBuf, const int* a, const int* b)
{
	while (*a != 0  && * b != 0) {
		sum += *b;

		*pBuf++ = (*b) + '0';
		*pBuf++ = ' ';
		*pBuf = 0;

#ifdef _DEBUG
		printf( ":%d:", *b );
#endif
		if (sum == 10) {
			printf("%s[%d]成功\n", buf, sum);

			return sum;
		} else if (sum > 10) {
			printf("%s[%d]失敗\n", buf, sum);

			return sum;
		}

		calc(sum, pBuf, a, b);

		while (*b != 0) {
			b++;
			if (*b == 0) {
				break;
			}
			else
			{
#ifdef _DEBUG
				printf("$%d$", *b);
#endif
				calc(sum, pBuf, a, b);
			}
		}
	}
	return sum;
}


int
main() try
{
	const int	array[] = {5, 4, 3, 2, 0};
	const int*	ptr = array;

	clearBuf();

	int i = 0;
	while ( array[ i ] > 0 ) {
		calc(0, buf, &array[ i ], &array[ i ] );
		i++;
	}

	return EXIT_SUCCESS;
}

catch (...)
{
	return EXIT_FAILURE;
}

// end.

5 5 [10]成功
5 3 2 [10]成功
4 4 2 [10]成功
4 3 3 [10]成功
4 2 2 2 [10]成功
3 3 2 2 [10]成功
2 2 2 2 2 [10]成功

の 7 通り

であってるみみ ?
」

[usao]

> 7 通り

最初に {5} とかも例示されている，すなわち，（ぴったり10にする必要は無くて）余りを出してもいいという話だと思うから違うんじゃない？

[あたっしゅ]

東上☆海美☆「

コード:

//
// https://dixq.net/forum/viewtopic.php?f=3&t=21547
// 組み合わせ？のプログラムの考え方が分かりません！！ - ミクプラ(ja)
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


const int	BUFMAX = 5 * 2 + 1;
char		buf[ BUFMAX ];


int
calc(int sum, char* pBuf, const int* a, const int* b)
{
	while (*a != 0  && * b != 0) {
		sum += *b;

		*pBuf++ = (*b) + '0';
		*pBuf++ = ' ';
		*pBuf = 0;

#ifdef _DEBUG
		printf( ":%d:", *b );
#endif
		if (sum == 10) {
			printf("%s[%d]成功\n", buf, sum);

			return sum;
		} else if (sum > 10) {
#ifdef _DEBUG
			printf("%s[%d]失敗\n", buf, sum);
#endif
			return sum;
		} else {
			printf("%s[%d]\n", buf, sum);
		}

		calc(sum, pBuf, a, b);

		while (*b != 0) {
			b++;
			if (*b == 0) {
				break;
			}
			else
			{
#ifdef _DEBUG
				printf("$%d$", *b);
#endif
				calc(sum, pBuf, a, b);
			}
		}
	}
	return sum;
}


int
main() try
{
	memset(buf, 0, BUFMAX);

	{
		const int	array[] = { 5, 4, 3, 2, 0 };
		const int*	ptr = array;
		int			i = 0;

		while ( *ptr > 0) {
			calc(0, buf, ptr, ptr );

			ptr++;
		}
	}

	return EXIT_SUCCESS;
}

catch (...)
{
	return EXIT_FAILURE;
}


// end.

5 [5]
5 5 [10]成功
5 4 [9]
5 3 [8]
5 3 2 [10]成功
5 2 [7]
5 2 2 [9]
4 [4]
4 4 [8]
4 4 2 [10]成功
4 3 [7]
4 3 3 [10]成功
4 3 2 [9]
4 2 [6]
4 2 2 [8]
4 2 2 2 [10]成功
3 [3]
3 3 [6]
3 3 3 [9]
3 3 2 [8]
3 3 2 2 [10]成功
3 2 [5]
3 2 2 [7]
3 2 2 2 [9]
2 [2]
2 2 [4]
2 2 2 [6]
2 2 2 2 [8]
2 2 2 2 2 [10]成功

29 通りで、空集合入れると 30 通りみみ。
」

[dic]

さすがですな

答えはどうなんだろう

[あたっしゅ]

東上☆海美☆「
よく考えてみると {5} と {5, 5} は、同じだから、

5 [5]
5 5 [10]成功

は、5 5 で同じ。

5 3 [8]
5 3 2 [10]成功
5 2 [7]
3 2 [5]

は、5 3 2 で同じ。

4 4 [8]
4 4 2 [10]成功
4 2 [6]

は、4 4 2 で同じ。


4 3 [7]
4 3 3 [10]成功
3 3 [6]

は、4 3 3 で同じ。

4 2 2 [8]
4 2 2 2 [10]成功

は、4 2 2 2 で同じ。

3 3 2 [8]
3 3 2 2 [10]成功
3 2 2 [7]

は、3 3 2 2 で同じ。

2 2 2 2 [8]
2 2 2 2 2 [10]成功

は、2 2 2 2 2 で同じ。
とりあえず、手動でやってみたみみ。
かなり減るな。
」

[あたっしゅ]

東上☆海美☆「
＞3 3 2 [8]
＞3 3 2 2 [10]成功
＞3 2 2 [7]
＞
＞ は、3 3 2 2 で同じ。

3 2 2 [7] は、3 3 2 2 と同じじゃないな。


とりあえず、

5 5 [0]成功
5 4 1
5 3 2 [0]成功
5 2 2 1
4 6
4 4 2 [0]成功
4 3 3 [0]成功
4 3 2 1
4 2 2 2 [0]成功
3 7
3 3 3 1
3 3 2 2 [0]成功
3 2 2 2 1
2 8
2 2 6
2 2 2 2 2 [0]成功

と、出せるようになった。
」

[あたっしゅ]

東上☆海美☆「
#14＞ 3 2 2 [7] は、3 3 2 2 と同じじゃないな。

3 2 2 [7] は、3 2 2 3 だから 3 3 2 2 と同じだな。
」