동적 계획 (선택 값 집계)

질문 설명:
한 그룹의 수 (예 를 들 어 3, 34, 4, 12, 5, 2) 와 S (예 를 들 어 9) 를 지정 합 니 다. 주어진 수 에서 몇 개의 수 를 선택 하여 S 로 합 칠 수 있다 면 1 을 출력 합 니 다. 그렇지 않 으 면 0 을 출력 합 니 다.
문제 분석:
 이 문 제 는 분명히 동적 계획 문제 이 고 뒤의 숫자 선택 은 앞의 숫자 와 s 와 관련 이 있다.따라서 상태 전이 방정식 을 확정 할 수 있다. 뒤의 숫자 를 선택 할 때 앞의 선택 숫자 는 s 로 이 숫자 를 줄 일 수 있어 야 한다. 이 숫자 를 선택 하지 않 을 때 앞에서 선택 한 숫자 는 s 로 만 들 수 있 고 상태 전이 방정식 을 확정 한 후에 재 귀 법 과 비 전달 법 으로 해 를 구 할 수 있다.비 재 귀 법 은 배열 을 사용 하여 앞에서 계산 한 내용 을 저장 하면 재 귀 로 인해 발생 하 는 대량의 중복 계산 을 피 할 수 있 고 연산 속 도 를 크게 가속 화 할 수 있다.
실행 코드 는 다음 과 같 습 니 다:

#include
using namespace std;
bool opt1(int *a, int n, int s); //   
bool opt2(int *a, int n, int s);  //    
///6 3 34 4 12 5 2 9


int main()
{
	int n, *a, s, i;
	cin >> n;
	a = new int [n];
	for(i = 0 ; i < n; i++)
	{
		cin >> a[i];
	}
	cin >> s;
	cout << opt1(a, n-1, s) << endl << opt2(a, n, s);
}

bool opt1(int *a, int n, int s)
{
	if(s == 0) // s 0，      
	{
		return true;
	}
	else if(n == 0)
	{
		return s == a[n]; //         ，       s，         
	}
	else if(a[n] > s) 
	{    //            ，        ，          
		return opt1(a, n - 1, s);
	}
	else
	{    //         ，            ，         
		return opt1(a, n - 1, s - a[n]) || opt1(a, n - 1, s);
	}
}

bool opt2(int *a, int n, int s)
{
	int i, j;
	bool **b; //      ,                ,  0      s+  
	b = new bool * [n];
	for(i = 0; i < n; i++)
	{
		b[i] = new bool [s+1];
	}
	for(i = 0; i < n; i++)
	{
		b[i][0] = true; //     s 0   ，        0 
	}
	for(i = 0; i <= s; i++)
	{
		if(a[0] == b[0][i])
		{
			b[0][i] = true; //     a[i] s       
		}
		else
		{
			b[0][i] = false; //        
		}
	}
	for(i = 1; i < n; i++)
	{
		for(j = 1; j <= s; j++)
		{
			if(a[i] > j)
			{
				b[i][j] = b[i-1][j]; //         ，      
			}
			else
			{    //    ，    ，           
				b[i][j] = b[i-1][j] || b[i-1][j-a[i]];
			}
		}
	}
	return b[n-1][s]; //     ，   n      s 
}