[Dovelet][DP] 01knapsack

01knapsack

http://59.23.113.171/30stair/01knapsack/01knapsack.php?pname=01knapsack

<코드>

#include <stdio.h>
int Dp[101][10010] = {};
 
struct jjj{
    int weight;
    int value;
};
 
 
int main(void){
 
    int N;
    int jNum;
    jjj jew[110] = {};
 
    scanf("%d", &N);
    scanf("%d", &jNum);
    for (int i = 0; i < jNum; i++)
        scanf("%d %d", &jew[i].weight, &jew[i].value);
 
 
    for (int i = 0; i < jNum; i++){
        for (int j = 0; j <= N; j++){
        
            if (j - jew[i].weight >= 0){
                if (Dp[i][j] < jew[i].value + Dp[i][j - jew[i].weight])
                    Dp[i + 1][j] = jew[i].value + Dp[i][j - jew[i].weight];
                else
                    Dp[i + 1][j] = Dp[i][j];
            }
            else
                Dp[i + 1][j] = Dp[i][j];
        }
    }
 
    printf("%d\n", Dp[jNum][N]);
    return 0;
}

<문제 푼 요령>

1. 이 문제의 중점은 차례대로 보석들을 검색하는데 그 보석을 썻을때와 안썻을때를 비교해서 가장 큰값을 비교하면 된다.

2. 2차원 Dp 테이블을 만들어서 각 테이블에 그 순서의 보석을 썻을때의 최대치 값을 쭈욱 적어놓은다. 

3. 그 후 그 이전의 보석을 가졌을때의 값을 이용하여서 현재의 보석을 가졌을때의 최대치를 비교 할 수 있다.

4. 그렇게 구한 마지막인 Dp[보석수][가방무게] 가 최대값으로서 결과값을 얻을 수 있다.