[더블릿] KnapSack

프로그램 명: 01knapsack

제한시간: 1 초

도둑이 보석상에 침입하여 보석을 훔쳐가려고 한다. 그런데 보석이 가져 갈수 있는 보석의 무게(n)은 한정되어 있다.

각각의 보석의 무게(weight)와 값(value)을 가지고 있다. 무게 n 으로 어떤 보석을 가져 가는게 가장 많은 이윤(?)을 취할 수 있는 가를 구하는게 문제이다.

단, 보석은 쪼갤 수 없고 종류당 하나씩 있다고 하자.

입력 방법

입력의

• 첫 줄에는 도둑이 가져갈 수 있는 무게를,
• 다음 줄에는 보석의 개수,
• 다음 줄 부터는 각 보석의 무게와 값이 한 줄에 하나씩 입력된다.

가방의 크기는 10000 이하이고 , 보석의 개수는 100 개 이하 무게와 가격은 200 이하의 정수이다.

출력 방법

첫 줄에 최대 이윤을 출력한다.

입출력 예

입력

30
3
5 50
10 60
20 140

출력

200




#include <stdio.h>
#define MAX 31
 
 
    int arr[MAX][MAX]={0},w[MAX]={0},p[MAX]={0};
    int i,j,n,m;
 
int main()
{
    scanf("%d %d",&m,&n);
 
    for(i = 1; i <= n; i++)
        scanf("%d %d",&w[i],&p[i]);
 
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++){
            if(w[i] <= j && arr[i-1][j] <= arr[i-1][j-w[i]]+p[i])
                arr[i][j] = arr[i-1][j-w[i]]+p[i];
            else
                arr[i][j] = arr[i-1][j];
        }
 
    printf("%d\n",arr[n][m]);
 
    return 0;
}

물건 있다고 친다면

a 5 50

b 10 60

c 20 140

가방의 사이즈 별로 a만의 이윤을 구함

5 : 50

6 : 50

7 : 50

8 : 50

9 : 50

10: 50

...

가방의 사이즈 별로 a와 b만의 이윤을 구함

5 : 50

6 : 50

7 : 50

8 : 50

9 : 50

10 : 60

11 : 60

12 : 60

13 : 60

14 : 60

15 : 110

16 : 110

17 : 110

18 : 110

19 : 110

20 : 110

...

여기서 값을 a만의 이윤을 구한 표의 똑같은 자리와 이윤을 비교하여 값을 넣으면 됩니다.

가방의 사이즈 별로 a와 b와 c만의 이윤을 구함

5 : 50

6 : 50

7 : 50

8 : 50

9 : 50

10 : 60

11 : 60

12 : 60

13 : 60

14 : 60

15 : 110

16 : 110

17 : 110

18 : 110

19 : 110

20 : 140

21 : 140

22 : 140

23 : 140

24 : 140

25 : 140

26 : 140

27 : 140

28 : 140

29 : 140

30 : 200

...

값을 구할 가방의 사이즈는 30이니 

답은 200

답 : 200

이렇게 풀면 됩니다.

구해 놓은 값을 참조하는 전형적 다이나믹 알고리즘 문제입니다.