devbelly

문제 https://www.acmicpc.net/problem/1231 알고리즘 knapsack 풀이 $D$일동안 갯수제한없는 knapsack을 하는 문제입니다. 그리디한 DP임을 눈치채야 풀 수 있습니다. A일에 사서 B일에 파는 것은 A+1일에 해당 주식을 팔지 말지 결정하고 팔았다면 무조건 재매수를 하는 것을 B일까지 반복하는 것과 동일합니다. 만일 10 15 20에 해당하는 주식이 있다면 10에 주식을 사서 3일째 되는 날 20에 팔아 10의 이득을 챙기는 것과 2일째에 15에 팔고 다시 15에 사서 20에 파는 것은 동일합니다. 즉 갯수제한이 없는 knapsack을 D-1일 동안 하는 것과 동일한 문제로 바뀌게 됩니다. $cache[i]$= 현재 사용가능한 돈이 $i$원일때, 얻을 수 있는 최대..

문제 https://www.acmicpc.net/problem/12865 알고리즘 knapsack 풀이 갯수제한이 있는 01 knapsack 문제입니다. $cache[i]$=현재 담은 무게가 $i$ 일때 얻을 수 있는 최대가치 안쪽 포문을 역순으로 고려하면 갯수를 하나 택할 때 상황만을 고려할 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> K; rep(i, N) rep(j, 2) cin >> bag[i][j]; rep(i, N) { for (int j = K; j >= bag[i][0]; --j) { cache[j] = max(cache[j], cache[j..

문제 https://www.acmicpc.net/problem/6066 알고리즘 Knapsack 풀이 갯수제한이 없는 01 Knapsack 문제입니다. $cache[i][j]$ = $i$번째 물건까지 택하고 현재 얻은 hay양이 $j$ 일때 지불해야하는 최소 금액 으로 가정하면 풀 수 있습니다. $cache[i][j]$가 갱신하는 다음 상태는 현재 상태에서 hay를 구매했을때 상태인 $cache[i][j+hay]$ 와 현재 물건을 택하지 않고 다음 물건을 택하는 $cache[i+1][j]$가 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> H; rep(i, N) ..