동적 계획 의 최대 K 곱 하기 문제

제목 요구
설정 I 는 n 비트 10 진수 입 니 다.I 를 k 단 으로 나 누 면 k 개의 정 수 를 얻 을 수 있다.이 k 개의 정수 곱 하기 를 I 의 k 곱 하기 라 고 한다.주어진 I 와 k 에 대해 I 의 최대 k 곱 하기 알고리즘 을 시험 적 으로 설계 합 니 다.예 를 들 어 십 진법 정수 1234 를 3 단 으로 나 누 면 다음 과 같은 상황 이 있 을 수 있다.× 2 × 34 = 68 1 × 23 × 4 = 92 12 × 3 × 4 = 144
대체적인 사고 방식.
최 우수 원 리 를 만족 시 키 는 것 을 증명 한다. 가설 최대 k 곱 하기 는 앞의 x 위 를 k - 1 단 으로 나 누고 마지막 정 수 를 곱 하 는 것 이다.만약 에 앞의 x 위의 구분 이 가장 좋 은 방법 이 아니라면 그 곱 은 반드시 최 적 화 된 방법 으로 얻 은 곱 하기 S 보다 작 을 것 이다.max 는 마지막 정수 소득 결과 와 최대 k 곱 하기 가 아니 라 전제 와 모순 된다.따라서 앞의 x 위 를 k - 1 단 소득 결과 비 로 나 누 어 최대 곱 하기 로 한다.[동적 계획 문제 에서 최 우수 원리 에 대한 증명 은 주로 반증 법 을 사용한다] 동적 계획 함수 령 number (i, j) 를 확정 하면 i 위 에서 j 위 정수 로 구 성 된 (j - i + 1) 비트 정 수 를 나타 낸다.produt (p, q) 은 앞 p 비트 정수 가 q 세그먼트 로 나 뉘 어 얻 은 최대 곱 하기 임 을 나타 낸다.[구분 단수 가 정수 자리수 보다 크 면 결 과 는 0]
초기 하위 문제: (q = 1 시) produt (p, 1) = number (1, p) 는 몇 개의 정수 에 관 계 없 이 한 단락 으로 나 뉘 어 있 으 며, 최대 k 곱 하기 는 모두 그 자체 입 니 다.다음 단계 의 문제: (q > 1 및 q < = p 시) product (p, q) = max {product (x, q - 1) * number (x + 1, p)} (1 < = x < = p - 1) p 는 정수 로 q 단 으로 나 뉘 어 각각 앞의 x 비트 이 수 를 q - 1 단 소득 의 최대 곱 하기 와 나머지 세그먼트 의 곱 하기 로 나 누 어 적당 한 데이터 구조 기록 을 선택 한 다음 비교 하면 가장 큰 결 과 는 produt (p, q) 이다.
리스트
q\p
1
2
3
4
1
1
12
123
1234
2
0
2
36
492
3
0
0
6
144
4
0
0
0
24
첫 번 째 줄 은 정 수 를 한 단락 으로 나 누고 결 과 는 그 자체 이다.두 번 째 줄 product (2, 2) = max {product (1, 1) * number (2, 2)} = 2;product(3,2)=max{product(1,1)*number(2,3), product(2,1)*number(3,3)}=max{1*23,12*3}=36; product(4,2)=max{product(1,1)*number(2,4),product(2,1)*number(3,4),product(3,1)*number(4,4)}=max{1*234,12*34,123*4}=492; 세 번 째 줄 product (3, 3) = max {product (2, 2) * number (3, 3)} = 6;product(4,3)=max{product(3,2)*number(4,4),product(2,2)*number(3,4)}=max{36*4,2*34}=144; 네 번 째 줄 product (4, 4) = max {product (3, 3) * number (4, 4)} = 24;
q\p
3
31
312
1
3
31
312
2
0
3
62
c + + 소스 코드 구현

#include
#include
using namespace std;

//          n k         
//                 
void getnumber(int number[20],int num,int n)
{
	int b = 0;
	for (int a = n-1; a>=0; a--)
	{
		b = num % 10;
		num = num / 10;
		number[a] = b;
	}
	return;
}
//  p q         
int countnumber(int p, int q,int *number)
{
	int newnumber = 0;
	for (int a=p;a<=q;a++)
	{
		newnumber = newnumber* 10+number[a];
	}
	return newnumber;
}
int main()
{
	int k; int n; int num;
	int number[20];
	int product[20][20];
	ifstream f1("C:\\Data\\1.txt");
	ofstream f2("C:\\Data\\2.txt");
	f1 >> n;
	f1 >> k;
	f1 >> num;
	getnumber(number, num, n);
	if (k == 1)//             
	{
		cout << "  k   " << num << "
";
		f2 << "  k   " << num << "
";
		return 0;
	}
	for (int temp = 0; temp < n; temp++)
	{
		product[0][temp] = countnumber(0, temp, number);
	}
	for (int i = 0; i < n; i++)//i  
	{
		for (int j = 1; j < k; j++)//j  
		{
			if (j > i)
			{
				product[j][i] = 0;
				break;//         
			}
			if (j <= i)
			{
				int max = 0; int temp = 0;
				for (int a = i-1; a >= 0; a--)
				{
					int nnum = countnumber(a + 1, i, number);
					temp = nnum * product[j - 1][a];
					if (temp > max)
						max = temp;//        
				}
				product[j][i] = max;
			}
		}
	}
	cout << "  k      " << product[k-1][n-1] << "
";
	f2 << "  k      " << product[k - 1][n - 1] << "
";
	f1.close();
	f2.close();
	return 0;
}