개요

[링크]백준 12865번: 평범한 가방

• 입력
  첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

  입력으로 주어지는 모든 수는 정수이다.

• 출력
  한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

접근 방식

[동전 2 문제] 와 유사하게 재귀 함수인 solution함수에
지금까지 가방에 넣은 무게, n번째 item인지를 인자로 넘겨주었다.

//현재 타겟무게가 targetweight일때, n번째부터 끝까지 중에서 최대 가치
int solution(int targetWeight, int n) 

그 후 매 재귀 마다 해당 아이템을 넣고 재귀를 실행할 경우와
안 넣고 재귀를 실행하는 경우에서의 최댓값을 구하여 dp배열에 저장해줬다.

탑 다운 방식 코드

#include<iostream>
#include<vector>
#include<memory.h>
#include<algorithm>

using namespace std;
//물품의 수
const int N = 101;
//버틸수 있는 무게
const int K = 100'001;
//dp배열, 입력받은 물품 수, 들 수 있는 최대 무게
int dp[K][N], inputN = 0, inputK = 0;

//무게,가치 입력받은값 저장하는 벡터
vector<pair<int, int>> v;

void input() {
	int  temp1 = 0, temp2 = 0;
	cin >> inputN >> inputK;

	for (int i = 0; i < inputN; i++) {
		cin >> temp1 >> temp2;
		v.push_back(make_pair(temp1,temp2));
	}
	//dp배열 -1로 초기화
	memset(dp, -1, sizeof(dp));
}

//현재 타겟무게가 targetweight일때, n번째부터 끝까지 중에서 최대 가치
int solution(int targetWeight, int n) {
	//dp 참조
	int& ret = dp[targetWeight][n];
	//ret이 이미 저장되어있다면 return;
	if (ret != -1) return ret;
	// 끝을 넘어가면 최대가치는 0
	if (n == inputN) {
		ret = 0;
		return ret; 
	}

	//기본적으로 ret에는 아이템 안 넣었을 때 값 저장 (이식으로 인해 맨 마지막까지 간 후 차근차근 걔산해서 돌아옴)
	ret = solution(targetWeight, n + 1);

	//max함수의 left는 n번째물품을 포함했을때, right는 n번째 물품을 포함 안했을 때
	//targetweight에 현재 무게 더했을 때 inputK를 넘는지 확인해야함!
	if(targetWeight+v[n].first <= inputK) ret = max(solution(targetWeight+v[n].first , n + 1 )+ v[n].second , ret);

	return ret;
}

int main() {
	input();
	int ans=solution(0,0);
	cout << ans;
}

바텀 업 방식 코드

#include<iostream>				
#include<algorithm>

using namespace std;

int dp[101][100'001];	
//가치값 입력받을 배열
int value[101];
//무게값 입력받을 배열
int weight[101];

int main() {								
	int maxWeight, amount=1;	
	cin >> amount >> maxWeight;

	for (int i = 1; i <= amount; i++) {
		cin >> weight[i] >> value[i];
	}
	
	for (int i = 1; i <= amount; i++) {	
		for (int j = 1; j <= maxWeight; j++) {
        //탑다운 방식과 동일하게 i,j에 현재값 안넣은 값과 현재값 넣었을때 나눠서 넣어줌
			if (j >= weight[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]]+value[i]);
            //만약 maxweight를 넘었다면 값 더하지말고 이전값 넣기
			else dp[i][j] = dp[i-1][j];
		}
	}

	cout << dp[amount][maxWeight];
}

문풀후생

처음으로 헤맨 곳은 넣었을 때와 안 넣었을 때 비교하는 부분인

if(targetWeight+v[n].first <= inputK) ret = max(solution(targetWeight+v[n].first , n + 1 )+ v[n].second , ret);

이 line에서 현재 무게를 체크하는 조건문인 if(targetWeight+v[n].first <= inputK) 를
안 적어서 계속 틀렸었다. 결국 인터넷을 찾아서 비슷하게 푼 분의 코드를 보니
단순히 앞에 targetWeight가 inputK보다 크다면 return 0을 해주기만 해서 답이 계속 안나왔다.

두 번째로 헤맨 건 왜인진 아직도 모르겠는데
위와같이 코드를 작성했는데 백준 문제에서의 예시 답이 계속 13이 나왔다.
그래서 계속 원인 생각하느라 시간을 허비했었는데 인터넷의 다른 답을 가지고 실행을 해본후
ctrl z로 원래대로 되돌리고 실행하니 답이 정상적으로 14가 나왔다.
아직도 어이가 없다.

23년 2월 3일 추가) 다시 풀어보려 했을 땐 백트래킹으로 접근을 하였고,

void backtracking(int totWeight, int totValue, int vIndex) {
	if (totWeight > K)	return;
	maxValue = maxValue > totValue ? maxValue : totValue;
	if (vIndex == N) return;
	//넣고 진행
	totWeight += v[vIndex].weight;
	totValue += v[vIndex].value;
	backtracking(totWeight, totValue, vIndex + 1);
	//넣고 진행한 후에 다시 빼줌
	totWeight -= v[vIndex].weight;
	totValue -= v[vIndex].value;
	//아무것도 안 넣고 진행
	backtracking(totWeight, totValue, vIndex + 1);
}

이런식으로 아예 모든 케이스를 조사하는식으로 했으나 당연히 시간초과가 나온다.
모든 값을 넣고 안 넣고의 경우의 수는 총 2^amount경우가 나오므로 답이없다.

따라서 고민해본 결과 백트래킹을 사용할때는 모든 케이스를 탐색하여
해당 케이스가 몇개 있는지 찾는다던지 이런식으로 꼭 모든 케이스를 다 돌아야할때 사용하고,

이 문제같은 경우는 해당케이스에서 최대값을 찾는 방식이므로,
끝에서부터 계속 최대값을 갱신해주면 끝값은 다시 탐색할 필요가없어서
시간이 더욱 절약된다.

레퍼런스

kks227님의 깃허브- 12865문제