[알고리즘] (동적 계획법) 0-1 배낭 문제(0-1 knapsack problem)

https://jeonyeohun.tistory.com/86

[알고리즘 정리] 배낭 문제(Knapsack Problem)

 

예제로는 [백준 12865번] 평범한 배낭을 참고한다.

이 문제는 NP-hard문제이다.

optimazation problem 모든 경로를 탐색하여 최적해를 찾는 문제!! DP를 이용해야겠지??

경로: 해당 무게로 만들 수 있는 조합

값: V가치

1. top - down 방식

 

2. bottom - up 방식

tabulation 3가지 방법 (최적화)

3. 알고리즘 분석

 

 

https://hi-guten-tag.tistory.com/160

[알고리즘 - 이론] 0-1 KnapSack Problem and Fractional KnapSack Problem (0-1 배낭 문제, 분할 가능한 배낭 문제)

 

 

최적화 끝판왕

#include<stdio.h>
#define MAX(a,b) ( ( (a) > (b) ) ? (a) : (b) )

int n, k;
int imp[1000], cost[1000];
int knap[2][10001];
int ptr;

int main(){
    scanf("%d %d", &n, &k);
    for(int i = 0; i < k; i++){
        scanf("%d %d", &imp[i], &cost[i]);
    }
    for(int j = cost[0]; j <= n; j++)   knap[0][j] = imp[0];
    for(int i = 1; i < k; i++){
        ptr = i%2;
        for(int j = 0; j < cost[i]; j++)    knap[ptr][j] = knap[1-ptr][j];
        for(int j = cost[i]; j <= n; j++){
            knap[ptr][j] = MAX(knap[1-ptr][j], imp[i] + knap[1-ptr][j-cost[i]]);
        }
    }
    printf("%d", knap[ptr][n]);
    return 0;
}