동적 계획 의 계란 던 지기 (또는 핸드폰) 문제

끌어들이다
계란 2 개 를 100 층 에서 아래로 던 져 계란 의 경 도 를 측정 한다.예 를 들 어 달걀 이 9 층 에서 깨 지지 않 고 10 층 에서 깨 지면 달걀 이 깨 지지 않 는 임계 점 이 9 층 이다.
― 계란 이 깨 지지 않 는 임계 점 을 어떻게 최소 의 시도 횟수 로 측정 할 수 있 을 까?
분석 하 다.
주의: 문제 의 하 나 는 이 최소 횟수 에 포함 되 어 있 으 므 로 반드시 측정 할 수 있 습 니 다.
이 문 제 를 완벽 하 게 해결 하 는 사고방식 은 먼저 역방향 가설 에 가장 좋 은 x 가 존재 하 는 것 이다. 첫 번 째 는 x 층 부터 던 져 야 한다.왜 x 층 부터 던 져 요?
만약 에 첫 번 째 로 x + 1 층 에 던진다 고 가정 하면 첫 번 째 계란 이 깨 지면 두 번 째 계란 은 1 층 부터 1 층 씩 던 져 서 x 층 까지 만 던 질 수 있다.이렇게 되면 우 리 는 모두 x + 1 번 을 시 도 했 고 가설 시도 x 번 과 어 긋 났 다.이 를 통 해 알 수 있 듯 이 처음 버 리 는 층 은 x + 1 층 보다 작 아야 한다.
만약 에 첫 번 째 로 x - 1 층 에 던진다 고 가정 하면 첫 번 째 계란 이 깨 지면 두 번 째 계란 은 1 층 부터 한 층 씩 던 져 서 x - 2 층 까지 만 던 질 수 있다.이렇게 되면 우 리 는 모두 x - 2 + 1 = x - 1 번 을 시 도 했 고 가설 시도 x 번 과 똑 같 습 니 다.
만약 에 첫 번 째 로 x 층 에 던진다 고 가정 하면 첫 번 째 계란 이 깨 지면 두 번 째 계란 은 1 층 부터 한 층 씩 던 질 수 밖 에 없다 (이것 이 마지막 계란 이기 때문에 더 이상 위험 을 무릅 쓰 고 층 을 사이 에 두 고 던 질 수 없다). x - 1 층 까지 던 질 수 있다.이렇게 되면 우 리 는 모두 x - 1 + 1 = x 회 를 시 도 했 는데 마침 가설 횟수 를 초과 하지 않 았 다.
이제 두 번 째 는 어떻게 던 져 야 되 지?먼저 첫 번 째 를 던 진 결 과 는 두 가지 가 있 는데 하 나 는 계란 이 깨 진 것 이 고 그 다음 에 1 층 부터 위로 던 집 니 다.둘째, 계란 이 깨 지지 않 았 습 니 다. 모두 x 번 을 던 져 야 하기 때문에 전에 이미 한 번 버 렸 기 때문에 그 다음 에 x - 1 번 을 던 져 야 합 니 다. 그러면 문 제 는 100 - x 층 높이 의 위층 에서 최소 x - 1 번 을 버 리 면 어떻게 버 려 야 하 는 지 로 바 뀌 었 습 니 다.같은 생각 에 따라 x - 1 층 에 던 집 니 다. 여기 의 x - 1 대응 은 바로 실제 x + (x - 1) 층 입 니 다.이 사고방식 에 따라 계속 조작 을 반복 하 는데 마지막 으로 던 진 층 수 는 100 층 이 어야 하기 때문에 다음 과 같은 관계 식 이 생 겼 다.
x+(x-1)+(x-2)+...+1=100
모두 x 항 이 있 는데 x 를 풀 면 14 와 같 습 니 다. 이것 이 바로 최종 답 입 니 다.
본론
N 개의 계란 과 M 층, 계란 이 깨 지지 않 는 임계 점 을 찾 으 려 면 몇 번 을 시도 해 야 합 니까?
분석 하 다.
만약 에 dp [N] [M] 이 최 악의 운 에서 가장 많이 테스트 해 야 하 는 횟수 와 같다 고 가정 하면 우 리 는 처음으로 x 층 에 던 졌 다. 그러면 두 가지 가능성 이 있다. 만약 에 계란 이 깨 지면 dp [N] [M] = dp [N] [N] [1] [x - 1] + 1 이 있 고 계란 이 깨 지지 않 으 면 dp [N] [M] = dp [N] [M - x] + 1 이 있다.우리 가 원 하 는 것 은 '운 이 가장 나쁘다' 는 상황 에서 가장 좋 은 방안 에서 가장 많은 테스트 횟수 를 필요 로 하기 때문에 dp [N] [M] 은 max (dp [N - 1] [x - 1] + 1, dp [N] [M - x] + 1) 와 같 아야 한다.한편, x 는 불확실 한 숫자 입 니 다. 그의 수치 범 위 는 (0 < = x < = M) 이 고 x 의 수치 가 방안 의 우열 을 결정 합 니 다. 방안 이 가장 좋 으 려 면 가장 적당 한 x 값 을 취해 야 합 니 다. 즉, dp [N] [M] 을 최소 화 할 수 있 기 때문에 있 습 니 다.
dp[N][M]=min{max(dp[N-1][x-1]+1，dp[N][M-x]+1) | 0<=x<=M}
위의 방정식 은 동적 계획 에 필요 한 상태 전이 방정식 이다.
전체 문제 풀이 코드

#include
#include
using namespace std;

//N   ，M   
void solve(int N,int M){
	if(N<1||M<1)	return;
	
//	      
	int dp[N+1][M+1];

//	       ，        	
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			dp[i][j]=j;
		}
	}
	
	for(int i=2;i<=N;i++){
		for(int j=2;j<=M;j++){
			int tmp=dp[i-1][j];
			for(int x=1;x<=j;x++){
//				tmp  1 x          
				tmp=min(tmp,max(dp[i-1][x-1]+1,dp[i][j-x]+1));			
			}
			dp[i][j]=tmp;
		}
	}
	cout<

최적화 하 다.
N 번 째 계란 의 답 을 얻 으 려 면 사실 N - 1 개의 계란 을 찾 았 을 때의 상황 만 찾 아야 하고, 첫 번 째 계란 에서 N 번 째 계란 까지 의 상황 을 전부 기록 할 필요 가 없 기 때문에 배열 은 dp [2] [M + 1] 의 공간 을 신청 하면 된다.이렇게 하면 공간의 복잡 도 를 낮 출 수 있다.
같은 유형의 문제: 테스트 횟수
x 별의 주민 들 은 성격 이 그다지 좋 지 않 지만 다행히 그들 이 화가 났 을 때 유일한 이상 한 행동 은 핸드폰 을 떨 어 뜨리 는 것 이다.각 대기업 들 도 잇달아 각종 내 동 형 휴대 전 화 를 내 놓 았 다.x 별의 질량 감독 국 은 휴대 전 화 는 반드시 내 충격 테스트 를 거 쳐 내 충격 지 수 를 평가 한 후에 야 출시 유통 을 허용 하도록 규정 했다.
x 별 에는 구름 속으로 우뚝 솟 은 높 은 탑 이 많아 서 내 굴 테스트 를 할 수 있다.탑의 각 층 높이 는 모두 같다. 지구 상에 서 조금 다른 것 은 그들의 1 층 은 지면 이 아니 라 우리 의 2 층 에 해당 한다.
휴대 전화 가 7 층 에서 떨 어 졌 지만 8 층 에서 떨 어 졌 다 면 휴대 전화 내 역 지수 = 7.특히 휴대 전화 가 1 층 에서 떨 어 지면 고장 나 면 내 낙 지수 = 0.만약 탑의 최고 층 n 층 에 가서 던 졌 는데 망 가지 지 않 았 다 면, 내 던 지기 지수 = n.
테스트 횟수 를 줄 이기 위해 공장 마다 휴대 전화 3 대 를 추출 하여 테스트 에 참가한다.
어떤 테스트 의 탑 높이 는 1000 층 이다. 만약 에 우리 가 항상 최선 의 전략 을 사용한다 면 최 악의 운 에서 최대 몇 번 을 테스트 해 야 핸드폰 의 내 떨 림 지 수 를 확정 할 수 있 습 니까? 
이 최대 테스트 횟수 를 기입 해 주세요.
주의: 기입 해 야 할 것 은 하나의 정수 이 며, 어떠한 여분의 내용 도 기입 하지 마 세 요.
분석 하 다.
이것 은 제9 회 블 루 브리지 컵 의 제목 으로 기본적으로 조끼 를 바 꾸 었 는데 사고방식 과 계란 던 지기 문 제 는 똑같다.계란 던 지기 문 제 를 풀 었 다 면 아주 덩어리 로 만 들 수 있 었 을 텐 데 안 타 깝 게 도 나 는 없 었 다.
전체 문제 풀이 코드

#include
#include
using namespace std;

int main(){
//	3   ，1000  ，          
	int dp[4][1001];
//	        
	for(int i=0;i<4;i++){
		for(int j=1;j<=1000;j++){
			dp[i][j]=j;
		}
	}
	
//	
	for(int i=1;i<4;i++){
		for(int j=1;j<=1000;j++){
//			tmp  1 x         ，      i-1   ，j         
			int tmp=dp[i-1][j];
			for(int x=1;x<=j;x++){
				tmp=min(tmp,max(dp[i-1][x-1]+1,dp[i][j-x]+1));
			}
			dp[i][j]=tmp;
		}
	}
	
	cout<

운행 결 과 는 13.
 
 
본 고 는 아래 두 편의 위 챗 푸 시 를 참고 하 였 다.

만화: 재 미 있 는 계란 던 지기 문제

만화: 동태 계획 으로 계란 던 지기 문제 해결