[백준] 12865번 평범한 배낭 (= plain backpack) - 재우스 프로그래밍 (C 언어)

문제 링크 : www.acmicpc.net/problem/12865

#include <stdio.h>
#include <stdlib.h>

#define DEBUG 0
#define MAX_OBJECT_COUNT 100
#define MAX_WEIGHT_BAG 100000

typedef struct _Node {
    int mWeight;
    int mValue;
} Node;

//input 물품과 무게를 저장하는 배열
Node arrInput[MAX_OBJECT_COUNT + 1];
//arrInput에서 가지고 갈 수 있는 물건의 조합으로 가장 큰 value값
int DPmap[MAX_OBJECT_COUNT + 1][MAX_WEIGHT_BAG];
//N : 물품의 수량, K : 배낭이 버틸 수 있는 최대 무게
int N, K;
//Brute Force 알고리즘으로도 해결이 가능하나 시간 부족 발생
/*
//arrInput에 저장된 순서대로 물품을 넣을 수 있는 모든 방식을 넣어보고 최댓값을 계속 갱신하는 함수
//인자 Node: 현재 무게와 가치 상황이 저장된 Node
//인자 int: 함수 내에서 배낭에 넣을지 말지 고민할 무게, 가치의 index
void weightBruteForce(Node *, int);
void sortArrInput(void);
*/
//Dynamic Programming 알고리즘으로 N, K까지 DPmap을 채움
void DP(void);

int main(void)
{
    //arrInput의 index
    //int arrInputIdx = 0;
    //지속적으로 배낭 상황을 저장할 현재 Node
    Node *currentNode;
    currentNode = (Node *)malloc(sizeof(Node));
    currentNode->mWeight = 0;
    currentNode->mValue = 0;

    //input 저장하기
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &arrInput[i].mWeight, &arrInput[i].mValue);
    }
//Brute Force 방법으로 풀 때
/*
    //arrInput 오름차순으로 정렬
    sortArrInput();
    //가방에 넣을 수 있는 모든 경우의 수 탐색하기
    for (int i = 0; i < N; i++) {
        weightBruteForce(currentNode, i);
    }
    printf("%d\n", result);
*/
    DP();
    printf("%d\n", DPmap[N][K]);

    free(currentNode);
    return 0;
}

void DP(void)
{
    for (int i = 0; i <= N; i++) {
        for (int j = 0;j <= K; j++) {
#if DEBUG
            if (i > 0 && j > 0 && j - arrInput[i - 1].mWeight > 0 && j == 100000) {
            printf("i: %d, j: %d\n", i, j);
            printf("map[%d][%d]: %d\n", i - 1, j, DPmap[i - 1][j]);
            printf("map[%d][%d]: %d\n", i - 1, j - arrInput[i - 1].mWeight, DPmap[i - 1][j - arrInput[i - 1].mWeight]);
            printf("value: %d\n", arrInput[i - 1].mValue);
            }
#endif
            //물건이 0개이거나 가방 허용 무게가 0이면 아무것도 넣을 수 없음.
            if (i == 0 || j == 0) {
                DPmap[i][j] = 0;
                continue;
            }

            //새로 추가되는 물건의 무게가 현재 배낭 최대 무게보다 무거우면 새로 추가되는 물건은 절대 포함 될 수 없음.
            if (arrInput[i].mWeight > j) {
                DPmap[i][j] = DPmap[i - 1][j];
            }
            //새로 추가되는 물건의 무게가 현재 배낭 최대 무게는 넘지 않을 때
            else {
                //새로 추가되는 물건이 포함되지 않으면  value가 더 클 때
                if (DPmap[i - 1][j] > DPmap[i - 1][j - arrInput[i].mWeight] + arrInput[i].mValue) {
                    DPmap[i][j] = DPmap[i - 1][j];
                }
                //새로 추가되는 물건이 포함되면 value가 더 클 때
                else {
                    DPmap[i][j] = DPmap[i - 1][j - arrInput[i].mWeight] + arrInput[i].mValue;
                }
            }
        }
    }
    return;
}
/*
void weightBruteForce(Node *currentNode, int arrInputIdx)
{
    //현재 무게에서 인자의 무게까지 추가되면 배낭의 한계를 초과할 때
    if (currentNode->mWeight + arrInput[arrInputIdx].mWeight > K) {
        return;
    }
    //현재 무게, 가치 갱신
    currentNode->mWeight += arrInput[arrInputIdx].mWeight;
    currentNode->mValue += arrInput[arrInputIdx].mValue;

#if DEBUG
    printf("current W: %d, V: %d\n", currentNode->mWeight, currentNode->mValue);
    printf("result: %d, current idx: %d\n", result, arrInputIdx);
    printf("\n");
#endif

    //갱신된 현재 가치가 최대치라면 result 갱신
    if (result < currentNode->mValue) {
        result = currentNode->mValue;
    }

    //배열 순서대로 탐색
    for (int i = arrInputIdx + 1; i < N; i++) {
        if (currentNode->mWeight + arrInput[arrInputIdx + 1].mWeight > K) {
            break;
        }
        weightBruteForce(currentNode, i);
    }

    //현재 무게, 가치 backtracking
    currentNode->mWeight -= arrInput[arrInputIdx].mWeight;
    currentNode->mValue -= arrInput[arrInputIdx].mValue;

    return;
}

void sortArrInput(void)
{
    int tempWeight = 0, tempValue = 0;
    //배열의 맨 뒤부터 정렬이 되므로 0부터 i-1까지 정렬을 반복한다.
    for (int i = N; i > 0; i--) {
        for (int j = 0; j < i - 1; j++) {
            //앞에 있는 무게가 더 크면 swap 해준다.
            if (arrInput[j].mWeight > arrInput[j + 1].mWeight) {
                tempWeight = arrInput[j].mWeight;
                tempValue = arrInput[j].mValue;
                arrInput[j].mWeight = arrInput[j + 1].mWeight;
                arrInput[j].mValue = arrInput[j + 1].mValue;
                arrInput[j + 1].mWeight = tempWeight;
                arrInput[j + 1].mValue = tempValue;
            }
        }
    }
    return;
}
*/