[백준 14855] 만두 가게 사장 박승원

배낭문제 응용인가?

동일한 종류의 (weight, cost) 쌍이 여러개 있다면 각각 다른 row로 계산해도 되지만,

이번에는 (weight, cost, count)로 몇개인지도 묶어줘서 한 row로 한 개의 종류에 대한 계산을 다 할 수 있게 하였다.

            for (int count = 1; count <= cnt; count++)
            {
                // 만들 수 있는 갯수만큼만 고려
                if (total - count * weight < 0)
                {
                    break;
                }
                dp[i][total] = max(dp[i][total], dp[i - 1][total - weight * count] + cost * count);
            }