문제) N 개의 실수 A(1) ~ A(N)이 있을 때, 연속된 수 A(i) ... A(j)의 합이 최대가 되는 값을 구하라.


솔직히 Brute Force 방식으로 풀어도 O(N^3)의 복잡도를 가지므로,

NP-Complete 한 문제는 아니다.

하지만 D.P 연습으로 공부를 하는 거니깐.



D.P 문제 중에는 난이도가 낮은 문제가 아닐까?

반응형

설정

트랙백

댓글

  • MaxSum 2012.08.29 10:42 답글 | 수정/삭제 | ADDR

    You can calculate the sum in O(n) using Kadane's Algorithm.

    int a[n]; // randomized numbers

    int t = 0;
    int s = INT_MIN;
    int k = 0; l = 0;
    int j = 0;
    for(int i = 0; i < n; i++){
    t = t + a[i];
    if( t > s ){
    s = t;
    k = j; l = i;
    }
    if( t < 0 ){
    t = 0;
    j = i + 1;
    }
    }

    then s is max sum from k to l on 1D array

    • BlogIcon 아자 2012.08.30 10:07 신고 수정/삭제

      Wow, Thanks.
      I didn't know that algorithm.
      I'll modify my article.

- Knapsack Problem

Dynamic Programming을 공부하면서,

(정말 정말 너무나 쉬운) Fibonacci 수열의 값을 구하는 예를 제외하고,

가장 많이 이용되는 예가 아닐까?


열 마디 설명보다 그림이 이해하기 쉬우므로, 부담없이 인용할 수 있는 위키피디아 그림을 가져왔다.

File:Knapsack.svg
(저자: Dake, 출처: http://en.wikipedia.org/wiki/File:Knapsack.svg )


위 그림과 같이 15kg까지 담을 수 있는 배낭에

각각 Value와 Weight를 가진 N 종류 타입의 상자들을 담았을 때,

Max Value가 되는 값이 얼마인가? 를 구하는 문제이다.


Knapsack Problem에는 3가지 종류가 있다.

이 구분은 사용가능한 N 종류 타입의 아이템의 갯수에 따라 나뉜다.

(위 그림으로 치자면 상자의 각 타입의 상자가 몇 개씩 있느냐?)


1. 0-1 Knapsack Problem : N 개의 타입의 아이템이 1개씩 있음.

2. Bounded Knapsack Problem : N 개의 타입의 아이템이 x(임의의 갯수)개씩 있음.

3. Unbounded Knapsack Problem : N 개의 타입의 아이템의 갯수 제한이 없음.


기본적인 해결 아이디어는 동일하다.

하지만 종류에 따라 아이디어를 조금 간소화 시킬 수 있다.


3가지 방법에 대해 일반적으로 사용할 수 있는 Knapsack 소스는 다음과 같다.



결론

다시 한번봐도 어렵긴 마찬가지다.

여러가지 D.P 문제들을 보고 익숙해지길 바라는 수 밖에.



(추가사항)

Knapsack Problem 중에 아이템을 쪼갤수 있는 Case의 경우는,

Value/Weight 가 높은 순으로 Greedy 한 방법을 통해 해결할 수 있다.

반응형

설정

트랙백

댓글