[블루 브리지컵 홈페이지 시험문제-알고리즘 향상] 최대치(dp,0-1 가방) 구하기

문제집:
문제 설명
n개의 질서정연한 정수 쌍aibi를 주십시오. 선택한 모든 수의 ai+bi의 정수와 최대치를 선택해야 합니다.그리고 당신이 선택한 수 쌍의ai의 합과 비음,bi의 합과 비음을 요구합니다.
입력 형식
입력한 첫 번째 동작 n, 쌍의 개수 이하 n줄 줄마다 두 개의 정수aibi
출력 형식
선택한 숫자 쌍의ai+bi의 합을 출력합니다
샘플 입력
5 -403 -625 -847 901 -624 -708 -293 413 886 709
샘플 출력
1715
데이터 크기 및 규약
　　1<=n<=100 　　-1000<=ai,bi<=1000
시간 제한: 1.0s 메모리 제한: 256.0MB
문제 해결 보고서:
선택한 수의 ai+bi의 합을 직접 계산하지 않고 ai의 합과 일정한 상황에서 선택한 비의 합을 최대한 크게 계산하는 것으로 전환한다.그래서 01배낭 문제가 되었고ai의 값은 물체의 무게로,bi의 값은 이 물체의 가치로 되었다.먼저 모든 ai와 비가 0보다 적은 수쌍을 필터하고 dp[i][j][i][j]는 앞i의 수쌍을 표시하고 선택한 ai의 합이 j인 경우 비의 합의 최대값을 표시하고 dp[i][j][j]]를 -INF로 하고 모든 합법적인 상황을 초기화한다. dp[i][a[i][a[a]]]=b[i]], 그 다음에 dp[i][i][j] = max(dp[i-1][j], dp[i] [j], dp[j][[[j]]]]]), 만약에 j-a[[i]]가 존재하면 [dpi] [[j] [[dpi] [[[[dpi] [j] [[dpi] [j] [[[[[j]]][[[[j-a[i]]+b[i]).마지막으로 오프셋 제로를 통일적으로 추가합니다.주의해야 할 것은 이 가방 문제도 1차원으로 최적화할 수 있지만 필요없다. 만약에 1차원으로 최적화한다면 이 문제에 대한 코드는 더욱 세련되지 않고 오히려 복잡하게 될 것이다. 왜냐하면 이 문제를 초기화할 때 2차원 그룹의 첫 줄만 초기화할 수 없고 각 줄마다 하나의 값을 초기화해야 하기 때문에 가장 좋은 방법은 바로 2차원 그룹을 열어 가장 소박한 01배낭을 만드는 것이다.그리고 이 문제는 공간이 충분하기 때문에 MLE 문제를 걱정할 필요가 없다.
AC 코드: (약 78MB 공간)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
int tot;
int a[101],b[101];
int dp[101][200000 + 5];//    i ，a[i]  j    ，b[i]      
int zero = 100000;
const int INF = 0x3f3f3f3f;
int main()
{
	int n;
	cin>>n;
	for(int x,y,i = 1; i<=n; i++) {
		scanf("%d%d",&x,&y);
		if(x < 0 && y < 0) continue;
		a[++tot] = x, b[tot] = y;
	} 
	for(int i = 0; i<=tot; i++) {
		for(int j = -100000; j<=100000; j++) {
			dp[i][j+ zero] = -INF;
		}
	}
	for(int i = 1; i<=tot; i++) {
		dp[i][a[i]+ zero] = b[i];
	}
	for(int i = 2; i<=tot; i++) {
		for(int j = -100000; j<=100000; j++) {
			if(dp[i-1][j+ zero] != -INF) dp[i][j+ zero] = max(dp[i][j+zero],dp[i-1][j+ zero]);
			if(j - a[i] + zero >= 0 && j - a[i] + zero <= 200000) //     。 
				dp[i][j+ zero] = max(dp[i][j+ zero] , dp[i-1][j-a[i]+ zero] + b[i]);
		}
	}
	int ans = 0;
	for(int j = 100000; j>=0; j--) {
		if(dp[tot][j+ zero] >= 0) ans = max(ans, dp[tot][j+ zero] + j);
	}
	printf("%d
",ans);
	return 0 ;
 }

또는 다음과 같이 하십시오. (공간 162.9MB)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
int tot;
int a[MAX],b[MAX];
int dp[105][400000 + 5];//    i ，a[i]  j    ，b[i]      
int zero = 100000;
const int INF = 0x3f3f3f3f;
int main()
{
	int n;
	cin>>n;
	for(int x,y,i = 1; i<=n; i++) {
		scanf("%d%d",&x,&y);
		if(x < 0 && y < 0) continue;
		a[++tot] = x, b[tot] = y;
	} 
	for(int i = 0; i<=tot; i++) {
		for(int j = -100000; j<=300000; j++) {//    
			dp[i][j+ zero] = -INF;
		}
	}
	for(int i = 1; i<=tot; i++) {
		dp[i][a[i]+ zero] = b[i];
	}
	for(int i = 2; i<=tot; i++) {
		for(int j = -100000; j<=100000; j++) {
			if(dp[i-1][j+ zero] != -INF) dp[i][j+ zero] = max(dp[i][j+zero],dp[i-1][j+ zero]);
			if(j - a[i] + zero >= 0 )//    
				dp[i][j+ zero] = max(dp[i][j+ zero] , dp[i-1][j-a[i]+ zero] + b[i]);
		}
	}
	int ans = 0;
	for(int j = 100000; j>=0; j--) {
		if(dp[tot][j+ zero] >= 0) ans = max(ans, dp[tot][j+ zero] + j);
	}
	printf("%d
",ans);
	return 0 ;
 }

또는 다음과 같이 하십시오.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
int tot;
int a[MAX],b[MAX];
int dp[105][400000 + 5];//    i ，a[i]  j    ，b[i]      
int zero = 100000;
const int INF = 0x3f3f3f3f;
int main()
{
	int n;
	cin>>n;
	for(int x,y,i = 1; i<=n; i++) {
		scanf("%d%d",&x,&y);
		if(x < 0 && y < 0) continue;
		a[++tot] = x, b[tot] = y;
	} 
	for(int i = 0; i<=tot; i++) {
		for(int j = -100000; j<=300000; j++) {
			dp[i][j+ zero] = -INF;
		}
	}
	dp[0][zero] = 0;
//	for(int i = 1; i<=tot; i++) {
//		dp[i][a[i]+ zero] = b[i];
//	}
	for(int i = 1; i<=tot; i++) {
		for(int j = -100000; j<=100000; j++) {
			if(dp[i-1][j+ zero] != -INF) dp[i][j+ zero] = max(dp[i][j+zero],dp[i-1][j+ zero]);
			if(j - a[i] + zero >= 0 )
				dp[i][j+ zero] = max(dp[i][j+ zero] , dp[i-1][j-a[i]+ zero] + b[i]);
		}
	}
	int ans = 0;
	for(int j = 100000; j>=0; j--) {
		if(dp[tot][j+ zero] >= 0) ans = max(ans, dp[tot][j+ zero] + j);
	}
	printf("%d
",ans);
	return 0 ;
 }

물론 if(j-a[i]+zero>=0)도 쓰고 싶지 않다면 ZERO를 200000으로 설정하면 된다.
요약:
우선 0-1배낭과 차이가 있는지 알아야 한다. 0-1배낭은 -INF로 초기화하지 않아도 되지만 그렇게 표시하는 것은 표시할 수 있는 최대 가치(가치가 모두 정수이기 때문)이기 때문에 0은 불법 상태라고 볼 수 있다.이 문제는 반드시 -INF로 초기화해야 한다. 이른바'가치'는 마이너스일 수 있기 때문에 우리는 불법 상태를 새로 설정하고 유일한 합법적인 상태를 dp[0][zero]=0으로 설정해야 한다.뒤에 옮기기 편하게.사실 이렇게 말하면 1차원 0-1 가방으로 바꿀 수 있다.
오류 코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
int tot;
int a[MAX],b[MAX];
int dp[400000 + 5];//    i ，a[i]  j    ，b[i]      
int zero = 100000;
const int INF = 0x3f3f3f3f;
int main()
{
	int n;
	cin>>n;
	for(int x,y,i = 1; i<=n; i++) {
		scanf("%d%d",&x,&y);
		if(x < 0 && y < 0) continue;
		a[++tot] = x, b[tot] = y;
	} 
	for(int j = -100000; j<=300000; j++) {
		dp[j+ zero] = -INF;
	}
	dp[zero] = 0;
	for(int i = 1; i<=tot; i++) {
		for(int j = 100000; j>=-100000; j--) {
			if(j - a[i] + zero >= 0) dp[j+ zero] = max(dp[j+ zero] , dp[j-a[i]+ zero] + b[i]);
		}
	}
	int ans = 0;
	for(int j = 100000; j>=0; j--) {
		if(dp[j+ zero] >= 0) ans = max(ans, dp[j+ zero] + j);
	}
	printf("%d
",ans);
	return 0 ;
 }

그러나 자세히 생각해 보면 이것은 잘못된 것이다. 왜냐하면 그 자리에서 굴러가는 전제는 뒤의 수는 앞의 수만 쓸 수 있다는 것이다. 그리고 너의 이 문제는 a[i]가 플러스와 마이너스가 있기 때문에 앞의 상태를 사용할 수도 있고 뒤의 상태를 사용할 수도 있기 때문에 일차원으로 최적화할 수 없다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

동적 기획 문제 풀이의 일반적인 사고방식

동규로 돌아가는 일반적인 전환 방법 귀속 함수에는 n개의 매개 변수가 있는데 하나의 n차원의 수조를 정의한다. 수조의 다음 표는 귀속 함수 매개 변수의 수치 범위이고 수조 원소의 값은 귀속 함수의 귀환 값이다. 이렇...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[블루 브리지컵 홈페이지 시험문제-알고리즘 향상] 최대치(dp,0-1 가방) 구하기

좋은 웹페이지 즐겨찾기