배낭 채우기 문제

n개의 물건이 있다.

각 물건은 무게와 가치가 정해져있다.

 

무게는 w[n]={...}, 가치는 p[n]={...}이다.

W = 배낭에 넣을 수 있는 총 무게라고 할 때,

 

"W<=물건 무게의 합"을 유지하면서, 물건 가치의 합이 최대가 되도록 물건들의 집합을 구하자.

 

---

이 문제는 브루트포스 알고리즘을 사용하면...

n개의 물건에 대한 부분집합의 수는 2^n개이므로 복잡도가 너무 커진다.

 

그리디 알고리즘을 사용하면...

가장 비싼 물건부터 넣어도, 가장 가벼운 물건부터 넣어도, 무게당 가치가 가장 높은것부터 넣어도 해결할 수가 없다.

 

우리는 동적프로그래밍이나 분할정복법을 사용해야 한다.

 

물건에 각각 1~..n까지 번호를 붙이고, 번호를 i라고 하자.

전체 무게가 w를 넘지 않도록 i번째까지의 물건 중에서 얻은 최고의 이익을 P[i][w]라고 하자.

w==0일 때는, 물건을 넣지 말아야하므로 P[i][0] = 0이다.

i==0일 때는, 아무 물건도 넣지 못하므로 P[0][w]=0이다.

 

P[i][w] = max(P[i-1][w], P[i-1][w-wi] + p[i]) 이 된다.

i번째 물건을 넣지 않는 경우 = P[i-1][w] 이고,

i번째 물건을 넣는 경우 = P[i-1][w-wi] + p[i]이다.

 

int knapsack(int n,int w){
    if(n==0||w==0)
    	return 0;
    if(w[n]>w) //n번째 물건이 가방 최대 무게보다 무거움
    	return knapsack(n-1,w); //n번째 물건을 안 넣는 방법밖에 없음
    
    first = knapsack(n-1,w); //n번째 물건을 안 넣는 경우
    second = knapsack(n-1,w-w[n])+p[n]; //n번째 물건을 넣는 경우
    return max(first,second);

}

for(int i=0;i<=n;i++){
	for(int j=0;j<=w;j++){
		if(i==0||j==0)	dp[i][j]=0;
        else if(w[i]>j)	dp[i][j] = dp[i-1][j];
        else{
        	dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
        }
	}
}