Programming Contest Challenging8 중복 조합 n 종류의 물건이 있고 i번째 물건은 ai개 있습니다. 다른 종류의 물건끼리는 구별 가능합니다만, 같은 종류의 물건끼리는 구별 불가능합니다. 이들 물건 중에 m개를 골라 조합해 총수를 구하고M으로 나눈 나머지를 구하세요. 위의 문제는 다른 종류의 물건끼리는 구별이 가능하므로 아래와같이 점화식을 세울 수 있다. dp[i + 1][j] = i까지의 숫자를 이용하여 j개를 조합할 수 있는 총 갯수 i - 1번째 까지의 숫자를 이용하여 j - k개를 고르고 나머지 k개를 i번째 수에서 고르는 경우를 모두 더하면 i까지를 이용하여 j개를 고르는 모든 조합을 구할 수있다. dp[i + 1][j] = dp[i][j - k] (0 2017. 8. 10. LIS(최장 증가 부분열) 길이가 n인 수열 a0, a1, ... , an - 1이 있습니다. 이 수열의 증가 부분열 중 최장의 것의 길이를 구하세요. 단 증가 부분열이란 모든 i < j 에서 ai < aj를 만족하는 부분열을 말합니다. !제약 1 2017. 8. 9. 갯수 제한이 있는 부분합 n 종류의 수 a[i]가 각각 m[i]개씩 있습니다. 이들 중 몇개를 골라 그 합이 K가 될 수 있는지 판정합시다. !제약 1 2017. 8. 9. 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. 이전 1 2 다음