백준 12865 [C++]

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

1. 풀이방법

 

 - 처음에 떠올린 방법은 브루트 포스로 모든 경우의 수 (조합) 을 모두 계산해 보는 것 

 

 - 이렇게 짜볼까 하다가 시간초과가 매우 발생할 것 같아서 방향을 바꿨습니다.

 

 - 그냥 메모리를 사용해서 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블을 선언하자 라고 생각.

 

 - N개의 물건들을 하나씩 살펴 보면서 버틸 수 있는 무게 K 밑으로 살펴보며 이 물건을 넣어가며 테이블을 갱신

 

 

 

2. 주의사항

 

 - 아직 알고리즘 문제풀이가 많이 부족해서 기존의 떠오른 생각 방향에서 다른 쪽으로 생각하는게 부족...

 

 - 열심히 풀어야겠습니다...

 

 

3. 나의코드

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int N, K;
int dp[100001]; // 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블
int weightarr[101];
int valuearr[101];

void dypro() {
	for (int i = 1; i <= N; i++) {
		for (int j =K; j >= 0; j--) {
			if (weightarr[i]<= j) {
				dp[j] = max(dp[j], dp[j- weightarr[i]] + valuearr[i]);
			}
		}
	}
	cout << dp[K] << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> weightarr[i] >> valuearr[i];
	}
	dypro();
	return 0;
}