면접 100문제 시리즈의 14는 1부터 n까지 마음대로 몇 개의 수를 취하여 m로 합친다

1. 제목 설명: 두 개의 정수 n과 m를 입력하고 수열 1, 2, 3...n에서 임의로 몇 개의 수를 취하면 여기에서 같은 수를 중복해서 취하지 못하고 m와 같게 하여 그 중의 모든 가능한 조합을 열거하도록 요구한다.
문제 풀이 사고방식: 전형적인 0-1 가방 문제는 숫자마다 두 가지 상태가 있는데 취하거나 취하지 않는다.가장 간단한 것은 귀속으로 해답을 구하는 것이다.이곳의 역행 순서는 n에서 1까지입니다. 이렇게 하면 역귀의 출구를 판단하기 쉽고 물론 가지치기도 쉽습니다.핵심 코드는 다음과 같습니다. 예쁘다고 생각하십니까?

// 1~Num Sum 
void FindCombination(int *arr, int Index, int Sum, int Num)
{
	if(Sum < 1 || Num < 1)
		return;
	if(Sum < Num)
		Num = Sum;
	if(Sum == Num || Sum == 1)
	{
		arr[Index++] = Sum;
		Print(arr, Index);
		--Index;
		return;
	}
	// Num
	FindCombination(arr, Index, Sum, Num - 1);
	arr[Index++] = Num;
	// Num
	FindCombination(arr, Index, Sum - Num, Num - 1);
}

2, 제목이 확장됩니다. 위의 문제는 한 개의 숫자를 한 번만 뽑을 수 있도록 요구합니다. 만약에 한 개의 숫자를 마음대로 몇 번 뽑을 수 있다면 이런 조합은 몇 가지가 있습니까?이런 상황의 데이터는 매우 크기 때문에 구체적인 조합을 출력할 필요가 없고 종류의 수량만 제시하면 된다. 블로그
화폐 교환 문제는 바로 이 방법으로 해답을 구하는 것이다.이런 상황에서 모함수로 해답을 구하다.모함수에 관한 지식은 시간이 있으면 제가 보충해 드리겠습니다. 여러분이 모르시면 먼저 남겨두고 다음에 다시 보러 오세요.이런 문제에 관해서는 몇 가지 응용 상황이 있는데, 이전에 쓴 적이 있지만, 코드를 어디로 잃어버렸는지 모르니, 다음에 보충한다.
* 모든 숫자의 수량에 제한이 없으며 무한히 회수할 수 있습니다.
* 각 숫자는 수량 범위 내에서만 사용할 수 있는 수량을 지정합니다.이런 상황은 임의의 다항식의 전개와 유사하다.
핵심 코드는 다음과 같습니다.

// ， 1~Num Sum 
int GetNumOfSum(int Sum, int Num)
{
	if(Sum < 1 || Num < 1)
		return 0;
	if(Num > Sum)
		Num = Sum;
	int c1[N];
	int c2[N];
	int i,j,k;
	for(i = 0; i <= Sum; ++i)
		c1[i] = 1;
	memset(c2, 0, (Sum + 1) * sizeof(int));
	for(i = 2; i <= Num; ++i)
	{// 
		for(j = 0; j <= Sum; ++j)
		{// 
			for(k = 0; k + j <= Sum; k += i)
			{// 
				c2[k + j] += c1[j];
			}
		}
		memcpy(c1, c2, (Sum + 1) * sizeof(int));
		memset(c2, 0, (Sum + 1) * sizeof(int));
	}
	return c1[Sum];
}

3, 마지막으로 변수의 정의와main 함수의 호출을 제시합니다.

#include<stdio.h>
#include<string.h>
const int N = 30;
// 
void Print(int *arr, int nLen)
{
	if(!arr || nLen < 1)
		return;
	for(int i = 0; i < nLen; ++i)
		printf("%d ", arr[i]);
	printf("
");
}
int main()
{
	int arr[N];
	int n,m;
	while(scanf("%d %d", &n, &m) != EOF)
	{
		//FindCombination(arr, 0, m, n);
		printf(" ， %d 
", GetNumOfSum(m, n));
	}
	return 0;
}