[C] 12865: 평범한 배낭

Knapsack Problem은 학교 알고리즘 시간에 배웠어서 어떻게 해야하는지는 알고 있었는데..

 

푸는데 한시간 넘게 풀었다. 그에 대한 교훈이 뭐였냐..!

 

첫째, 웬만해서 전역변수로 배열을 초기화하자.. 배열의 범위만 넘어가지 않는 선에서 (약 2억) 가장 쉽고 따로 초기화 해주지 않아도 되된다.

둘째, 배열의 인덱스를 정할때 0부터 시작할지 혹은 1부터 시작할지를 확실히 정하고 시작하자.

셋째, 이차원배열도 효과적이지만 그냥 배열 2개를 따로 정하는게 헷갈리지 않는 경우가 있다.

 

이 문제도 점화식을 구하고, for문을 이용해서 작은문제들을 풀어 결국 결과까지 도출해내는 Bottom-Up방식을 사용했다.

밑에는 소스코드다..

 

#include <stdio.h>

int backpack[2][102];
int dp[102][100002];
int main(void)
{
  int n,max_w;
  scanf("%d %d",&n,&max_w);
 //int backpack[2][n+1];
  for(int i=1;i<n+1;i++)
    {
      scanf("%d %d",&backpack[0][i], &backpack[1][i]); //무게와 가치
    }
  //int dp[n+1][max_w+1];
  
  for(int i=1;i<n+1;i++)
    {
      for(int j=1;j<max_w+1;j++)
        {
          if(backpack[0][i]>j) //물건의 무게가 현재 가방의 용량보다 작은경우 
            dp[i][j]=dp[i-1][j];
          else //물건의 무게가 가방의 용량보다 커 어떻게 넣어야 가치가 최대일지 비교해야할때
          {
            if(dp[i-1][j]>dp[i-1][j-backpack[0][i]]+backpack[1][i]) //새롭게 물건을 가방에 넣는 경우가 이득이지 않을때
              dp[i][j]=dp[i-1][j];
            else //새롭게 물건을 가방에 넣는 경우가 이득일때
              dp[i][j]=dp[i-1][j-backpack[0][i]]+backpack[1][i];
            //현재의 가방무게한계에서 새로 들어올 물건의 물건을 뺏을때 가방의 가치합에서 새로운 물건의 가치합을 더한게 새로운 물건을 넣지 않았을 때보다 더 가치있는 경우다
          }
        }
    }
  /*for(int i=0;i<n+1;i++)
    {
      for(int j=0;j<max_w+1;j++)
        {
          printf("%d ",dp[i][j]);
        }
      printf("\n");
    }*/

  printf("%d",dp[n][max_w]);
}