필기시험 문제 26 - 이중 01 가방 문제

제목 설명: 빅 토 르 박 사 는 액체 상태 에 있 는 방사성 물질 을 사용 할 수 있 는 분열 원자 로 를 만 들 었 다.원자로 의 용량 은 V 갤 런 이다.그 는 N 병 의 방사성 액 체 를 가지 고 있 으 며, 각각 일정한 질량 과 일정한 부 피 를 가지 고 있다.액체 가 원자로 에 쏟 아 질 때 도 일부 단위 의 에너지 가 발생 한다.이제 빅 토 르 는 에너지 수출 을 극 대화 하려 고 한다.하지만 제한 조건 이 있다.그 는 원자 원소 의 물리 지식 과 역 사 를 연구 해 원자로 내 방사성 액체의 총량 이 특정 임계 질량 M 을 초과 해 서 는 안 되 며 그렇지 않 으 면 반응 이 통제 되 지 않 고 심 한 폭발 을 일 으 킬 수 있다 는 것 을 깨 달 았 다.그 가 목숨 을 잃 지 않도록 원자로 에서 가장 큰 에 너 지 를 얻 을 수 있 도록 알고리즘 을 써 라.입력: 이 함수 / 방법의 입력 은 여섯 개의 매개 변 수 를 포함 합 니 다. - reactorCap, 하나의 정수 로 원자로 의 용량 (V) 을 표시 합 니 다.numberOfRadLiquid, 하나의 정수 로 기 존의 작은 병 의 수량 (N) 을 표시 합 니 다.criticalMass, 하나의 정수 로 원자로 의 최대 임계 질량 (M) 을 나타 낸다.volumes, 하나의 정수 목록 으로 N 개의 방사성 액체의 부 피 를 순서대로 표시 합 니 다.masses, 하나의 정수 목록 으로 N 개의 방사성 액체의 질 을 순서대로 표시 합 니 다.energies, 하나의 정수 목록 으로 N 개의 방사성 액체 가 발생 하 는 에 너 지 를 순서대로 표시 합 니 다.출력: 주어진 제약 조건 에서 원자로 에서 발생 하 는 최대 에 너 지 를 나타 내 는 정 수 를 되 돌려 줍 니 다.예시: 입력: reactorCap = 100 numberOfRadLiquid = 5 criticalMass = 15 volumes = [50, 40, 30, 20, 10] masses = [1, 2, 3, 9, 5] energies = [300, 480, 270, 200, 180] 출력: 960 해석: 1, 2, 5 번 병 에 있 는 액 체 를 선택 하여 발생 하 는 에너지 = 300 + 480 + 180 = 960.이런 액체 조합 이 발생 하 는 총 부 피 는 = 50 + 40 + 10 = 100 으로 reactorCap 보다 크 지 않 고 원자로 의 총 질량 = 1 + 2 + 5 = 8 로 criticalMass 보다 크 지 않다.핵심 코드 는 다음 과 같 습 니 다.

#include 
#include 
#include 
#include 
using namespace std;
int dp[601][601][601];
int dp2[601][601];
//memset(dp, 0, sizeof(dp));
int maxEnergyGenerate(int V, int N, int M, int* volumes, int* masses, int* energies) {
	for (int i = 1; i <= N; i++) { //    		
		for (int j = V; j >= 0; j--) {  //     
			for (int k = M; k >= 0; k--) {  //      
				if (j - volumes[i - 1]<0 || k - masses[i - 1]<0) 
					dp[i][j][k] = dp[i - 1][j][k];
				else 
					dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - volumes[i - 1]][k - masses[i - 1]] + energies[i - 1]);
			}
		}
	}

	return dp[N][V][M];
}

int mytest(int v, int n, int m, int* volumes, int* masses, int* energies) {
	for (int i = 1; i <= n; i++) {
		for (int j = v; j >= volumes[i - 1]; j--) {
			for (int k = m; k >= masses[i - 1]; k--) {
				dp2[j][k] = max(dp2[j][k], dp2[j - volumes[i - 1]][k - masses[i - 1]] + energies[i - 1]);
			}
		}
	}
	return dp2[v][m];
}

int main() {

	int v = 100, n = 5, m = 15;
	int volumes[] = { 50,40,30,20,10 };
	int masses[] = { 1,2,3,9,5 };
	int energies[] = { 300,480,270,200,180 };
	
	cout << maxEnergyGenerate(v, n, m, volumes, masses, energies) << endl;
	cout << "new: " << endl;
	cout << mytest(v, n, m, volumes, masses, energies) << endl;
	return 0;
}