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

 

#include <iostream>

using namespace std;

int DP[100001];

int main(void)
{
	int n=0;
	int k=0;
	
	cin>>n>>k;
	
	for(int i=1; i<=n; i++)
	{
		int w=0;
		int v=0;
		cin>>w>>v;
		int temp[100001]={0};
		for(int j=1; j<=k; j++)
		{
			if(j-w>=0)
			{
				if(temp[j-1]<DP[j-w]+v)
				{
					temp[j]=DP[j-w]+v;
				}
				else
				{
					temp[j]=temp[j-1];	
				}			
			}
			else
			{
				temp[j]=temp[j-1];
			}
			if(DP[j]>temp[j])
			{
				temp[j]=DP[j];
			}
		}
		
		for(int i=1; i<=k; i++)
		{
			DP[i]=temp[i];
		}
		
	}
	
	
	cout<<DP[k];
	
	return 0;
}

 

기본적인 배낭문제이다. 배낭에 가장 가치가 크게 물건을 야무지게 넣는 것이 목표이다.

 

무게를 기준으로 진행한다.

i번째 물건이 들어왔을 때 가방의 무게를 1~k로 조절해서 물건을 최대한 넣는다.(가치가 가장 높게)

푸는 방법

1. 현재 가방 무게 - i번째 물건의 무게 >=0 즉 현재 가방에 i번째 물건을 넣을 수 있다면 (j-w>=0)

(현재가방 무게-1)의 가치<(이전 item 가방 무게 - i번째 물건의 무게)를 계산해서 (temp[j-1]<DP[j-w]+v) 

만약 DP[j-w]+v가 더 크다면 temp[j]=DP[j-w]+v를 실행하고 그게 아니라면 temp[j]=temp[j-1]를 실행한다.

무게는 큰데 가치가 낮은 경우에 어떻게 될지 생각해 보라.

 

이 과정을 마친 후에 마지막으로 DP[j]>temp[j]를 검사해줘야 한다. 만약 이전 값이 더 크다면 이전값으로 갱신한다.

(현재 아이템보다 이전 아이템을 사용했을 때 효율이 더 좋다는 뜻)

 

 

입력의 크기를 주의해서 보자. 

DP[101][100001] (XXX) 범위 초과

현재 item 가방과 이전 item 가방만 비교하면 된다.