Алгоритм для просчета наиболее выгодной скидки

[vulpio]

Есть 5 типов телефонов. Если покупаешь 2 разных то получаешь скидку в 5%, если 3 то 10%, если 4 то 20%, а если 5 разных то 25%. К примеру, если покупаешь 8 телефонов, 2 из которых одного типа, 2 второго, 2 третьего, 1 четвертого и 1 пятого, то наилучшая цена получится если использовать скидку при покупки 4-х одинаков телефонов два раза(4*8*0.8+4*8*0.8), а не скидку 5 разных и 3 разных телефонов.(5*8*0.75+3*8*0.1).

Подскажите пожалуйста, какой алгоритм будет самым оптимальным? Поскольку вариант, где нужно подсчитывать все комбинации, а потом выбирать самую оптимальную будет ужасным, если телефонов будет, скажем 20 штук. Спасибо.

[Dekay]

vector<double> dp(n+1);

vector<pair<int, int> > sale;
sale.pb(mp(2, 5));
sale.pb(mp(3, 10));
sale.pb(mp(4, 20));
sale.pb(mp(5, 25));

for(int i = 1; i <= n; i++) {
    dp[i] = dp[i-1]+1;
    forn(j, sz(sale)) {
        if (i >= sale[j].F) {
            dp[i] = min(dp[i], dp[i-sale[j].F]+sale[j].F*(100-sale[j].S)*1.0/100);
        }
    }
    cout << dp[i] << endl;
}

cout << dp[n] << endl;