Computer Science34 Unbounded Knapsack Problem(갯수 제한없는 배낭문제) 무게와 가격이 각각 Wi, Vi인 n개의 물건이 있습니다. 이 물건들로부터 무게의 총합이 W를 초과하지 않도록 선택했을 때의 가격 총합의 최대치를 구하세요. 단 같은 종류의 물건을 몇 개라도 고르는 것이 가능합니다. 일반적인 배낭문제를 생각하고 점화식을 정의하면 아래와 같다. dp[i + 1][j] = i번까지 물건 무게의 총합이 j 이하가 되도록 골랐을 때 가치의 최대치 dp[i][0] = dp[0][j] = 0 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]) (j >= k * w[i]) 이와 같은 점화식으로 코드를 구현하면 아래와 같다 int dp[MAX_N + 1][MAX_W + 1]; void solve() { for(int i = 0;.. 2017. 8. 4. 최장 공통 부분열(DP) 문자열 S1, S2, ... , Sn과 T1, T2, ... , Tn이 주어져 있습니다. 이 둘의 공통 부분 문자열의 길이의 최대 값을 구하세요. 단 문자열 S1S2...Sn의 부분 문자열이란 Si1, Si2, ... Sim(i1 < i2 < ... < im)로 표현 가능한 문자열을 말합니다. 제약 1 2017. 8. 4. 0/1Knapsack Problem(DP) DP(Dynamic Program, 동적계획법)을 이용하여 해결가능한 문제중 가장 기본적인 문제인 Knapsack Problem. 배낭문제의 유형으로는 0/1, bounded, unbounded, fractional 등이 있다. 무게와 가격이 각각 Wi, Vi,인 n개의 물건이 있습니다. 무게의 총합이 W를 초과하지 않도록 물건을 선택했을 때의 가격 총합의 최대치를 구하세요. 위 문제를 완전탐색을 이용하여 풀면 아래와같다. 각 물건 i를 선택하느냐 마느냐의 경우의 수가 존재한다. 1. i번째 물건을 배낭에 담지 않을 것이다. 2. 담을 수 있을경우 배낭에 담을 것이다. int n; int w[], v[]; //무게, 가격 //now부터 n -1까지 의 물건들을 용량이 capacity인 배낭에 담을때 //.. 2017. 8. 4. 탐욕(Greedy) 탐욕 알고리즘은 한가지 규칙에 의해 눈 앞에 보이는 최선만을 반복적으로 선택하여 최선의 결과를 얻어내는 알고리즘이다. 긴 널빤지를 N토막 내려고한다. L1, L2, ... , Ln이 자르려고 하는 널빤지의 길이이며 널빤지의 길이는 토막들의 합과 같다. 널빤지를 자를때에는 비용이 든다. 21을 13과 8로 자르는 비용은 21이다. 13을 5와 8로 자르는 비용은 13이다. N과 N개의 배열L이 주어질때 널빤지를 자를 수 있는 최소비용을 구하여라. 위 문제는 그리디를 이용하여 해결이 가능하다. 널빤지를 우리가 원하는 토막이 되게끔 자르다보면 마지막 토막이 나는 널빤지 조각이 있을 것이다. 여기에 주목하는 것이 이문제를 그리디로 풀 수 있는 요점이다. 예를들어 마지막 톱질로인해 널빤지조각이 a와b로 분리되었다.. 2017. 8. 3. 이전 1 ··· 5 6 7 8 9 다음