9.2_여행 짐 싸기_PACKING

문제 설명

algospot.com :: PACKING

• 캐리어의 용량 w (1 <= w <= 1000)가 있다.
• 캐리어에 넣고자 하는 물건 n(1 <= n <= 100)개가 주어진다.
• 각 물건의 부피(1 <= 부피 <= 1000)와 절박도(1 <= 절박도 <= 1000)가 주어진다.

=> 캐리어의 용량이 넘지 않게 물건을 넣을 때, 얻을 수 있는 최대 절박도 합과 가져갈 물건의 개수, 각 물건의 이름 출력하기

 

 

문제 풀이

Knapsack 문제

 

이 문제는 knapsack이라는 dp를 사용하는 대표 문제로 잘 알려져 있다.

 

dp에서 가장 중요한 것은 sub problem으로 문제를 쪼개는 것인데,

이 문제는 작게 봤을 때 한 물건에 대하여 넣기 or 넣지 않기 로 선택할 수 있다.

그리고 물건을 넣을 수 있는 경우는 캐리어의 용량이 해당 물건보다 클 때 넣을 수 있다.

 

물건의 개수(k)와 캐리어의 용량(W) 크기로 이루어진 2차원 배열(dp)를 만들고 다음과 같이 배열을 채울 수 있다.

 

i) W용량인 캐리어에 넣을 수 있을 때

dp[k][W] = dp[k-1][W-wk] + k의 만족도

ii) W용량인 캐리어에 넣을 수 없을 때

dp[k][W] = dp[k-1][W]

 

두 경우 중 큰 만족도를 가지는 것을 선택한다.

 

DP의 공간 줄이기

 

 

위의 코드를 보면 물건 k에 대해서 k-1행의 정보를 활용하여 k행을 채운다.

즉, 2행짜리 배열을 만든 후, 매 물건마다 최대 만족도를 구하고 윗줄로 한 칸씩 옮겨서 계산을 반복해준다면

k x W 크기가 아닌 2 x W 크기의 배열로 원하는 답을 구할 수 있다.

 

여기에 더해, 1줄짜리 배열로도 dp를 활용할 수 있다.

바로 연산 방향을 0 -> W가 아닌, W -> 0 의 역방향으로 연산해주면 된다.

이게 가능한 이유는 W용량인 캐리어에 대해 값을 알고 싶을 때, W보다 작거나 같은 열의 값을 이용하기 때문이다.

물건 k에 대하여

i) W용량인 캐리어에 넣을 수 있을 때

dp[W] = dp[W-wk] + k의 만족도

ii) W용량인 캐리어에 넣을 수 없을 때

dp[W] = dp[W]

임을 활용하면 1줄짜리 배열로 dp를 구성할 수 있다.

 

문제 풀이 코드

/*
	가져갈 수 있는 물건의 조합 중,
	무게 합이 무게 제한을 넘지 않는 묶음 중,
	그 중 절박도가 제일 높은 묶음

	Knapsack 문제
	1000 * 100은 공간 초과될 것 같으므로 2줄짜리로 구하자.

	역방향 dp는 한줄로 가능

*/

#include <iostream>
#include <string.h>

using namespace std;

struct Object {
	char objectName[21];
	int weight;
	int need;
};

Object objects[100];
int N, W;
int dp[1001];				// 무게에 따른 선호도
int objectCnt[1001];		// 무게에 따른 물건 개수
int objectIndexList[1001][100];		// 무게에 따른 물건 index 목록

void makeDP(int objectIndex) {
	Object ob = objects[objectIndex];
	for (int i = W; i > 0; --i) {
		if (ob.weight <= i) {
			if (dp[i] < dp[i - ob.weight] + ob.need) {
				dp[i] = dp[i - ob.weight] + ob.need;
				memcpy(objectIndexList[i], objectIndexList[i - ob.weight], sizeof(int) * 100);
				objectIndexList[i][objectCnt[i - ob.weight]] = objectIndex;
				objectCnt[i] = objectCnt[i - ob.weight] + 1;
			}
		}
	}
}

int main()
{
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		cin >> N >> W;
		for (int i = 0; i < N; ++i) {
			cin >> objects[i].objectName >> objects[i].weight >> objects[i].need;
		}
		memset(dp, 0, sizeof(dp));
		memset(objectCnt, 0, sizeof(objectCnt));
		for (int i = 0; i < N; ++i) {	// 각 물건을 넣을지 말지에 대한 연산
			makeDP(i);
		}
		cout << dp[W] << " " << objectCnt[W] << endl;
		for (int i = 0; i < objectCnt[W]; ++i) {
			cout << objects[objectIndexList[W][i]].objectName << endl;
		}
	}
	return 0;
}