[ 백준 12865] 평범한 배낭(C++)

12865번: 평범한 배낭

 

문제!

---

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

---

요약하면 무게가 정해진 가방에 물건을 채우는 과정에서 최대 가치의 값을 출력해주는 문제!

 

이번에도 어떤것을 dp에 저장할까 고민을 많이 했습니다.

 

처음에는 현재 남은공간에 따른 최대가치합을 저장해 줄려했으나

{ dp[현재 남은공간] = 최대가치합 }

 

도저히 모든 경우에 대해서 연산을 할수가 없어서 다음과 같이 바꿔 생각하였습니다.

 

int banang[101][100001] = { 0 }; // banang[사용][현재 남은 공간] = 최대 가치합 저장

 

그랬더니 한번에 풀리네요!

 

 

 

그럼 시작!

---

먼저 pair을 통해 받아주고 dp를 선언해줍시다.

vector <pair<int, int>> pro(101);// 무게와 가치

int banang[101][100001] = { 0 }; // banang[사용][현재 남은 공간] = 최대 가치합 저장

 

그 다음 입력을 받은 다음

 

 

메인부분!

for (int j = 1; j < max_w + 1; j++) {// 남은 무게
		for (int i = 1; i < n + 1; i++) {// 물품
			if (j >= pro[i].first) {// 넣을수 있다면
				banang[i][j] = max(banang[i - 1][j - pro[i].first] + pro[i].second, banang[i - 1][j]); // 최댓값 최신화
			}
			else {
				banang[i][j] = banang[i - 1][j];
			}
		}
	}

현재 물건을 넣었을때와 넣지 않았을때를 계속 비교해주어 모든 부분에 대해서 최신화를 시켜줍시다.

 

 

 

그렇게 끝까지 이동하면 제일 끝의 값이 최대값이 됩니다!

cout<< banang[n][max_w] << endl;

 

생각만 어렵고.... 코드는 짧고... 어지럽네요

 

ALL

#include <iostream>
#include <algorithm>

#include <vector>

using namespace std;
// 동적계획법 - > 직전의 정보를 현재의 정보를 구하는데 사용할수 있다 -- > 점화식이 존재 --> 단순한 앞뒤 계산가능할때

vector <pair<int, int>> pro(101);// 무게와 가치

int banang[101][100001] = { 0 }; // banang[사용][현재 남은 공간] = 최대 가치합 저장




int main() {
	int n;// 총 물품의수
	int max_w; // 무게 최대치
	int answer=0;


	cin >> n>> max_w;

	int num = 0;
	for (int i = 1; i < n+1; i++) {
		cin >> pro[i].first >> pro[i].second;
	}

	
	for (int j = 1; j < max_w + 1; j++) {// 남은 무게
		for (int i = 1; i < n + 1; i++) {// 물품
			if (j >= pro[i].first) {// 넣을수 있다면
				banang[i][j] = max(banang[i - 1][j - pro[i].first] + pro[i].second, banang[i - 1][j]); // 최댓값 최신화
			}
			else {
				banang[i][j] = banang[i - 1][j];
			}
		}
	}
	
	
	

	cout<< banang[n][max_w] << endl;
}

 

 

 

 

이 문제가  동적계획법 1 단계의 마지막 문제네요 ㅎ

 

이번 단계를 풀어보면서 알아가는 점이라면

1. 동적계획법 = dp를 사용하기위해서는 앞뒤 간의 무언가 관계되어 연산이 가능해야 사용가능하다

2. dp의 원소에 어떤것을 넣을지를 생각해보면 좀더 쉽게 접근할수도 있을것 같다.

3. 완전 탐색으로는 도저히 시간초과를 해결할수 없을때! 한번 생각해보자!

4. 점화식을 만들수 있으면 가장 좋다!

 

이정도 인것 같네요 아직 부족하지만 다음 단계들도 풀어 나가겠습니다.

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!