문제풀이 노트(31)-수열 1, 2...n에서 임의로 몇 개의 수를 취하여 m와 같게 하다

문제 설명: 두 개의 정수 n과 m를 입력하고 수열 1, 2에서...n에서 임의로 몇 개의 수를 취하여 m와 같게 하고 그 중의 모든 가능한 조합을 열거하도록 요구한다.
사고방식: 이 문제는 사실 가방 문제의 변형이다. 본고는 두 가지 해법을 제시한다.
해법1: 귀속을 사용하면 효율이 좀 낮을 수 있다.문제의 풀이를 F(n,m)로 가정하면 두 개의 서브 문제 F(n-1,m-n)와 F(n-1,m)로 분해할 수 있다.이 두 문제에 대해 차례로 해답을 구하고 해답을 구하는 과정에서 조건에 부합되는 숫자 조합을 찾으면 인쇄한다.
해법2: 순환을 사용하면 사실은 모든 조합을 일일이 열거하는 것이다.n에 대해 조합수는 2^n이어야 한다.우리는 숫자 i로 조합을 표시할 수 있다.만약에 i=5의 2진 형식이 101이고 상응하는 조합은 {1,3}이다.즉, 2진법의 모든 사람은 하나의 숫자를 대표하고,bit0은 숫자 1을 대표하고,bit1은 숫자 2를 대표하며, 순서대로 유추한다.어떤 사람이 1이면 이 자리에 표시된 숫자가 선택되었음을 나타낸다.
참조 코드:

//  ：  1,2...n ， m
//  ： n ，m ，flag ，len flag 
//  ：    
void BagProblem_Solution1(int n, int m, int *flag, int len)
{
	if(n < 1 || m < 1)
		return;

	if(n < m)
	{
		flag[n-1] = 1;
		BagProblem_Solution1(n-1, m-n, flag, len); // n
		flag[n-1] = 0;
		BagProblem_Solution1(n-1, m, flag, len);   // n
	}
	else
	{
		flag[m-1] = 1;  //n>=m， m 
		for(int i = 0; i < len; i++)
		{
			if(flag[i] == 1)
				cout<<i+1<<' ';
		}
		cout<<endl;
		flag[m-1] = 0; // m， 。 n = 10,m = 8， {1, 7} ， ，{1,3,4} {1,2,5} 
		BagProblem_Solution1(m-1, m, flag, len);
	}
}

//  ：  1,2...n ， m
//  ： n ，m 
//  ：    
void BagProblem_Solution2(int n, int m)
{
	if(n < 1|| m < 1)
		return;
	if(n > m)
		n = m;

	int num = 1<<n;               // 
	for(int i = 1; i < num; i++)  // 
	{
		int sum = 0;
		int j, k;
		for(j = i, k = 1; j != 0; j>>=1, k++) // ， 
		{
			if(j&1)
				sum += k;
		}
		if(sum == m) // ， 
		{
			for(j = i, k = 1; j != 0; j>>=1, k++)
			{
				if(j&1)
					cout<<k<<' ';
			}
			cout<<endl;
		}
	}
}

테스트 프로그램을 제공합니다.

int main()
{
	int n, m;
	cout<<"please enter n and m : ";
	cin>>n>>m;

	int *flag = new int[n];
	for(int i = 0; i < n; i++)
		flag[i] = 0;

	BagProblem_Solution1(n, m, flag, n);
	cout<<endl;
	BagProblem_Solution2(n, m);
	delete [] flag;
	return 0;
}

본인은 블로그 글의 판권을 누리고 있으니, 전재하여 출처를 밝혀 주십시오http://blog.csdn.net/wuzhekai1985