Задача: Имеются три раствора полезного вещества с концентрациями [latex]p_{1}, p_{2}, p_{3}[/latex] каждый и стоимостью [latex]s_{1}, s_{2}, s_{3}[/latex] соответственно. Можно ли смешать их так, чтобы получить раствор с заданной концентрацией [latex]p[/latex] наименьшей стоимости [latex]s[/latex]?
Указание. Пусть [latex]\alpha_{1}, \alpha_{2}, \alpha_{3}[/latex]- долевые содержания растворов в смеси. Тогда для получения заданной концентрации [latex]p[/latex] необходимо [latex]p_{1}\alpha_{1} + p_{2}\alpha_{2} + p_{3}\alpha_{3}=p[/latex].
Кроме того, нужно учесть условие «комплектности смеси»: [latex]\alpha_{1} + \alpha_{2} + \alpha_{3} = 1[/latex]; [latex]\alpha_{1} \ge 0; \alpha_{2} \ge 0; \alpha_{3} \ge 0;[/latex]
При этих условиях необходимо найти наименьшее значение линейной функции: [latex]s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }[/latex].
С учётом ограничений задача сводится к минимизации линейной функции одного переменного на отрезке, однако искомые выражения и условия получаются достаточно громоздкими. Можно показать, что в решении будут участвовать не более двух растворов. Тогда достаточно среди вариантов:
а) [latex]\alpha_{1} = 0[/latex];
б) [latex]\alpha_{2} = 0[/latex];
в) [latex]\alpha_{3} = 0[/latex];
Выбрать оптимальный, и затем провести необходимые расчеты.
Тесты
|
1 |
2 |
3 |
p |
s |
Комментарий |
| [latex]p_{i}[/latex] |
0 |
0 |
0 |
0 |
10 |
Пройден |
| [latex]s_{i}[/latex] |
10 |
12 |
14 |
| [latex]p_{i}[/latex] |
0 |
10 |
30 |
0 |
10 |
Пройден |
| [latex]s_{i}[/latex] |
10 |
20 |
30 |
| [latex]p_{i}[/latex] |
15.3 |
49.2 |
51.6 |
37.4 |
29.56 |
Пройден |
| [latex]s_{i}[/latex] |
40 |
10 |
20 |
| [latex]p_{i}[/latex] |
30 |
30 |
30 |
40 |
Impossible |
Пройден |
| [latex]s_{i}[/latex] |
25 |
14 |
40 |
| [latex]p_{i}[/latex] |
20.3 |
20.3 |
20.3 |
20.3 |
30 |
Пройден |
| [latex]s_{i}[/latex] |
30 |
40 |
50 |
| [latex]p_{i}[/latex] |
30 |
40 |
50 |
20 |
Impossible |
Пройден |
| [latex]s_{i}[/latex] |
19 |
31 |
22 |
| [latex]p_{i}[/latex] |
20 |
60 |
80 |
40 |
40 |
Пройден |
| [latex]s_{i}[/latex] |
60 |
20 |
100 |
| [latex]p_{i}[/latex] |
20 |
50 |
90 |
50 |
15.71 |
Пройден |
| [latex]s_{i}[/latex] |
10 |
80 |
20 |
| [latex]p_{i}[/latex] |
10 |
60 |
90 |
62.5 |
62.5 |
Пройден |
| [latex]s_{i}[/latex] |
190 |
10 |
20 |
Код программы:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <cstdio> #include <algorithm> using namespace std; double c_price( double p, double p1, double s1, double p2, double s2 ) { //if given solutions' concentrations and the result are equal if ( p1 == p2 ) { if( p1 == p ) return min( s1, s2 ); return 0; } //else solve the system of equations double a1 = ( p - p1 ) / ( p2 - p1 ); if ( a1 > 1 || a1 < 0 ) return 0; double a2 = 1 - a1; return s1*a1+s2*a2; } int main() { double p1, p2, p3, f_p; double s1, s2, s3; scanf("%lf %lf %lf %lf", &p1, &p2, &p3, &f_p); scanf("%lf %lf %lf", &s1, &s2, &s3); if( f_p > max( p1, max( p2, p2 ) ) || f_p < min( p1, min( p2, p3 ) ) ) { printf("Impossible!\n"); return 0; } double s12 = c_price( f_p, p1, s1, p2, s2 ); double s13 = c_price( f_p, p1, s1, p3, s3 ); double s23 = c_price( f_p, p2, s2, p3, s3 ); if( !s12 && !s13 && !s23 ) { printf("Impossible!\n"); return 0; } double min_price = s12; if ( min_price > s13 && s13 ) min_price = s13; if ( min_price > s23 && s23 ) min_price = s23; printf("%.2lf", min_price); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
import java.util.*; import java.lang.*; import java.io.*; import java.math.*; class Ideone { public static double c_price(double p, double p1, double s1, double p2, double s2){ if(p1 == p2){ //if given solutions' concentrations are equal return p1 == p ? Math.min(s1, s2) : 0; } if(p1 == p || p2 == p){ //if some given concentration equals to needed return p1 == p ? s1 : s2; } double a1 = (p-p1)/(p2-p1); if(a1 > 1 || a1 < 0) return 0; //inconsistent data double a2 = 1-a1; return s1*a1 + s2*a2; } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); double[] p = new double[3]; double[] s = new double[3]; for(int i = 0; i < 3; i++) p[i] = in.nextDouble(); double f_p = in.nextDouble(); for(int i = 0; i < 3; i++) s[i] = in.nextDouble(); double s12 = c_price(f_p, p[0], s[0], p[1], s[1]); double s13 = c_price(f_p, p[0], s[0], p[2], s[2]); double s23 = c_price(f_p, p[1], s[1], p[2], s[2]); if(s[0] == 0 && s[1] == 0 && s[2] == 0) System.out.println("Impossible"); else{ double min_price = s12; if(s13 != 0) min_price = Math.min(min_price, s13); if(s23 != 0) min_price = Math.min(min_price, s23); System.out.printf("%.2f", min_price); } } } |
Метод решения:
Задача сводится к решению системы уравнений:
[latex]\begin{cases} p_{1} \alpha_{2} + p_{2} \alpha_{2} + p_{3} \alpha_{3} = p,\\ \alpha_{1} + \alpha_{2} + \alpha_{3} = 1,\\ s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }; \end{cases}[/latex]
Безусловно, из первых двух уравнений системы можно найти общее решение с одной свободной переменной. Тогда для решения понадобится отыскать минимум линейной функции одной переменной. Тем не менее, автор задачника советует упростить расчеты и сократить список переменных до двух. Поочерёдно приравнивая к нулю каждую из них, рассчитаем стоимость всех возможных вариантов состава смеси и выберем самый дешевый.
Аналитическое решение в данном случае тривиально:
[latex]\begin{cases} p_{i} \alpha_{i} + p_{j} \alpha_{j} = p,\\ \alpha_{i} + \alpha_{j} = 1; \end{cases} \Rightarrow \begin{cases} \alpha_{i} = \frac { p-p_{i} } { p_{j}-p_{i} },\\ \alpha_{j} = 1-\alpha_{i}; \end{cases} s = s_{i} \alpha_{i} + s_{j} \alpha_{j};[/latex]
Для большей наглядности применяется функция
c_price (calculate price), в теле которой рассмотрены крайние случаи:
1) Если [latex]p_{1}=p_{2}=p[/latex], то нужно выбрать раствор наименьшей стоимости.
2) Если [latex]p_{1}=p_{2} \ne p[/latex], то решений нет.
3) Если [latex]p_{1}=p \ne p_{2}[/latex], то [latex]s = s_{1}[/latex]. Аналогично в случае [latex]p_{2}=p \ne p_{1}[/latex].
4) Если доля раствора в смеси [latex]\alpha 1[/latex], то решений нет.
Подробности реализации:
Использовались данные целочисленного типа и данные с плавающей точкой (двойной точности, т.к. в условии задачи нет ограничений на значения переменных, лежащие в рамках здравого смысла.
Протестировать работу программы можно по ссылке.
Реализация на Java: http://ideone.com/qTQpMX
Related Images:
