엘리베이터에는 한번에 탑승 가능한 무게 제한이 있다. 엘리베이터에 탑승하기 위한 승객들이 대기하고 있고, 무게 제한을 만족하면서 최소한의 운행 횟수로 승객들을 운반해야한다. 가장 작은 운행 횟수를 구하는 문제를 동적 계획법으로 해결해보자. vi weight = { 86, 58, 76, 102, 91 }; int lim = 200; input 값으로 승객들의 무게 데이터와 엘리베이터의 무게 제한이 주어진다. pair best[1

배낭 문제는 특정 무게와 가치를 갖는 물건들이 주어질 때 배낭의 무게 제한을 만족하면서 가장 가치를 크게 하는 물건들의 조합을 찾는 전형적인 동적 계획법(Dynamic programming) 문제이다. int knapsack(vi weight, vi value, int limit) { vector ans(weight.size() + 1, vi(limit + 1, 0)); int row = weight.size(); int col = limit; weight.insert(weight.begin(), 0); value.insert(value.begin(), 0); //add sentinel value for (int i = 1; i