Ещё задача на перебор

дык, посчитать кол-во счастливых билетов )))

 

Добрый день!
Спасибо за интересную задачку. Решение без перебора.

PHP:

1. <?
2. $numberFullKvassBarrels =
3. $numberHalfKvassBarrels =
4. $numberEmptyBarrels =
5. $numberBarrelsPerCart = 7;
6. $carts = 3;
7. $totalKvassBarrels = $numberFullKvassBarrels + $numberHalfKvassBarrels * 0.5;
8. $totalKvassBarrelsPertCart = $totalKvassBarrels / 3;
9. $minKvassBarrelsPertCart = intval($numberBarrelsPerCart / 3);
10. $cart = 0;
11. while ($cart < $carts) {
12.     if($cart < 2)
13.     {
14.         if($cart == 0)
15.         {
16.             $full = $minKvassBarrelsPertCart;
17.             $half = ($totalKvassBarrelsPertCart - $minKvassBarrelsPertCart) / 0.5;
18.             $empty = $numberBarrelsPerCart - ($full + $half);
19.         }
20.         $numberFullKvassBarrels -= $full;
21.         $numberHalfKvassBarrels -= $half;
22.         $numberEmptyBarrels -= $empty;
23.     }
24.     else
25.     {
26.         $full = $numberFullKvassBarrels;
27.         $half = $numberHalfKvassBarrels;
28.         $empty = $numberEmptyBarrels;
29.     }
30.     $barrelsPerCart[$cart]["full"] = $full;
31.     $barrelsPerCart[$cart]["half"] = $half;
32.     $barrelsPerCart[$cart]["empty"] = $empty;
33.     $cart++;
34. }
35. echo "<pre> \$barrelsPerCart ";
36. print_r($barrelsPerCart);
37. /*
38. $barrelsPerCart Array
39. (
40.     [0] => Array
41.         (
42.             [full] => 2
43.             [half] => 3
44.             [empty] => 2
45.         )
46.  
47.     [1] => Array
48.         (
49.             [full] => 2
50.             [half] => 3
51.             [empty] => 2
52.         )
53.  
54.     [2] => Array
55.         (
56.             [full] => 3
57.             [half] => 1
58.             [empty] => 3
59.         )
60.  
61. )
62. */
63. ?>

Удачи!

 

Добавил решение ответом на вопрос: "Сколькими различными способами можно погрузить 21 бочку"
Получилось, что двумя.

PHP:

1. <?
2. $numberBarrelsPerCart = 7;
3. $carts = 3;
4.  
5. $totalKvassBarrels = $numberBarrelsPerCart * 1.5;
6. $totalKvassBarrelsPertCart = $totalKvassBarrels/3;
7. $minFullBarrelsPerCart = intval($numberBarrelsPerCart/3);
8. $fullsBarrelsinCart = [];
9. echo "<pre>";
10. echo "Methods of stacking barrels:<br>";
11. for ($full = $minFullBarrelsPerCart; $full <= $numberBarrelsPerCart; $full++) {
12.     for ($half = 1; $half <= $numberBarrelsPerCart; $half++) {
13.         $kvassBarrelsPertCart = $full + $half * 0.5;
14.         if($kvassBarrelsPertCart == $totalKvassBarrelsPertCart)
15.         {
16.             $empty = $numberBarrelsPerCart - ($full + $half);
17.             echo "Barrels in cart full: $full half: $half emty: $empty<br>";
18.             $fullsBarrelsInCart[] = $full;
19.         }
20.     }
21. }
22.  
23. echo "<hr>";
24.  
25. foreach($fullsBarrelsInCart as $nMethod => $full ){
26.     $numberFullKvassBarrels =
27.     $numberHalfKvassBarrels =
28.     $numberEmptyBarrels = $numberBarrelsPerCart;    
29.     $cart = 0;
30.     echo "<br>Method of stacking barrels: ",($nMethod + 1), "<br>";
31.     while ($cart < $carts) {
32.         if($cart < 2)
33.         {
34.             if($cart == 0)
35.             {
36.                 $half = ($totalKvassBarrelsPertCart - $full) / 0.5;
37.                 $empty = $numberBarrelsPerCart - ($full + $half);
38.             }
39.             $numberFullKvassBarrels -= $full;
40.             $numberHalfKvassBarrels -= $half;
41.             $numberEmptyBarrels -= $empty;
42.         }
43.         else
44.         {
45.             $full = $numberFullKvassBarrels;
46.             $half = $numberHalfKvassBarrels;
47.             $empty = $numberEmptyBarrels;
48.         }
49.         $barrelsPerCart[$cart]["full"] = $full;
50.         $barrelsPerCart[$cart]["half"] = $half;
51.         $barrelsPerCart[$cart]["empty"] = $empty;
52.         $cart++;
53.     }
54.     echo "\$barrelsPerCart ";
55.     print_r($barrelsPerCart);
56. }
57. /*
58.  
59. Methods of stacking barrels:
60. Barrels in cart full: 2 half: 3 emty: 2
61. Barrels in cart full: 3 half: 1 emty: 3
62.  
63. Method of stacking barrels: 1
64. $barrelsPerCart Array
65. (
66.     [0] => Array
67.         (
68.             [full] => 2
69.             [half] => 3
70.             [empty] => 2
71.         )
72.  
73.     [1] => Array
74.         (
75.             [full] => 2
76.             [half] => 3
77.             [empty] => 2
78.         )
79.  
80.     [2] => Array
81.         (
82.             [full] => 3
83.             [half] => 1
84.             [empty] => 3
85.         )
86.  
87. )
88.  
89. Method of stacking barrels: 2
90. $barrelsPerCart Array
91. (
92.     [0] => Array
93.         (
94.             [full] => 3
95.             [half] => 1
96.             [empty] => 3
97.         )
98.  
99.     [1] => Array
100.         (
101.             [full] => 3
102.             [half] => 1
103.             [empty] => 3
104.         )
105.  
106.     [2] => Array
107.         (
108.             [full] => 1
109.             [half] => 5
110.             [empty] => 1
111.         )
112.  
113. )
114. */
115. ?>

 

Спасибо за ответ. Вы же видели, я тоже в начале не заметил, что нужно найти несколько способов.
Ну это не важно. Главное не терять, что знаешь и учится пока живешь.
Удачи!

 

Переспал с последним решением и понял, что нужно всё переделать.
Определил варианты укладки в одну телегу.
Их получилось три. Затем сделал перебор этих вариантов, чтобы определить способы укладки.
Вот, что получилось:

Option of packing barrels in one cart:

Barrels full: 1; half: 5; emty: 1
Barrels full: 2; half: 3; emty: 2
Barrels full: 3; half: 1; emty: 3


1. Method of packing barrels in three carts

cart: 1 Barrels full:1; half:5; empty:1;
cart: 2 Barrels full:3; half:1; empty:3;
cart: 3 Barrels full:3; half:1; empty:3;

2. Method of packing barrels in three carts
cart: 1 Barrels full:2; half:3; empty:2;
cart: 2 Barrels full:2; half:3; empty:2;
cart: 3 Barrels full:3; half:1; empty:3;

Последняя версия кода:

PHP:

1. <?
2. $numberBarrelsPerCart = 7;
3. $carts = 3;
4. $totalBarrels = $numberBarrelsPerCart * $carts;
5. $totalKvassBarrels = $numberBarrelsPerCart * 1.5;
6. $totalKvassBarrelsPertCart = $totalKvassBarrels/3;
7. $minFullBarrelsPerCart = intval($numberBarrelsPerCart/3);
8. $BarrelsinCart = [];
9.  
10. ########################################################################
11. echo "<h4>Option of packing barrels in one cart:</h4>";
12. for ($full = 1; $full <= $numberBarrelsPerCart; $full++) {
13.     for ($half = 1; $half <= $numberBarrelsPerCart; $half++) {
14.         $kvassBarrelsPertCart = $full + $half * 0.5;
15.         if($kvassBarrelsPertCart == $totalKvassBarrelsPertCart)
16.         {
17.             $empty = $numberBarrelsPerCart - ($full + $half);
18.             echo "Barrels full: $full; half: $half; emty: $empty<br>";
19.             $BarrelsInCart[] = [$full, $half,$empty];
20.         }
21.     }
22. }
23. echo "<hr>";
24. ########################################################################
25. $k = count($BarrelsInCart);
26. $methods = [];
27. for($i0=0; $i0< $k; $i0++){
28.     for($i1=0; $i1<$k; $i1++){
29.         for($i2=0; $i2<$k; $i2++){
30.             $indArr = [$i0, $i1, $i2];
31.             sort($indArr);
32.             $indMethod = implode("",$indArr);
33.             if(checkMethod($indArr))
34.                 $methods[$indMethod] = $indArr;
35.         }
36.     }
37. }
38. ########################################################################
39. $barrelsName = ["full", "half", "empty"];
40. $nMethod = 1;
41. foreach($methods as $indArr){
42.     echo "<h4>$nMethod. Method of packing barrels in three carts</h4>";
43.     foreach($indArr as $cart => $ind){
44.         echo "cart: ", $cart + 1, " Barrels  ";
45.         foreach($BarrelsInCart[$ind] as $iB => $barrels){
46.             echo $barrelsName[$iB], ":","$barrels; ";
47.         }
48.         echo "<br>";
49.     }
50.     echo "<hr>";
51.     $nMethod++;
52. }
53. ########################################################################
54. function checkMethod($indArr){
55.     global $BarrelsInCart;
56.     global $carts;
57.     global $numberBarrelsPerCart;
58.     global $totalBarrels;
59.  
60.     $sum = array_fill(0, $carts,0);
61.     foreach($indArr as $i){
62.         foreach($BarrelsInCart[$i] as $j =>$barrels){
63.             $sum[$j] += $barrels;
64.             if($sum[$j]>$numberBarrelsPerCart)
65.             return false;
66.         }
67.     }
68.     return array_sum($sum) == $totalBarrels?true:false;
69. }
70. ?>

 

Похоже что то это не все варианты. В некоторых случая пустых бочек может и не быть. Вообще мера в "полбочки" не однозначная, поэтому 3.5 бочки кваса (столько по условиям задачи приходится на каждую телегу) нужно распределить по 7 бочкам в разных вариантах. Если взять минимальное количество в одной бочке 0,5 бочки кваса (3.5 / 0,5 = 7 частей на семь бочек, но не больше двух частей в одной боке) - то могут быть ситуации, когда в 7 бочках по 0,5 бочки кваса.
0,5 0,5 0,5 0,5 0,5 0,5 0,5
1 0,5 0,5 0,5 0,5 0,5 0
1 1 0,5 0,5 0,5 0 0
1 1 1 0,5 0 0 0

Но возможно не совсем понял задачу.

 

Спасибо.
Я понял, что на на всех телегах должно быть поровну бочек и кваса
т.е. на каждой телеге по 7 бочек и поровну кваса - по 3.5 бочки
Если на одной телеге положить 7 по 0,5 бочки кваса,
то двух других будет 4 и 3 полных бочки, что противоречит условию задачи.
Однако, ради интереса добавил такой вариант,

PHP:

1. echo "<h4>Option of packing barrels in one cart:</h4>";
2. for ($full = 0; $full <= $numberBarrelsPerCart; $full++) {
3.     for ($half = 1; $half <= $numberBarrelsPerCart; $half++) {
4.         $kvassBarrelsPertCart = $full + $half * 0.5;
5.         if($kvassBarrelsPertCart == $totalKvassBarrelsPertCart)
6.         {
7.             $empty = $numberBarrelsPerCart - ($full + $half);
8.             echo "Barrels full: $full; half: $half; emty: $empty<br>";
9.             $BarrelsInCart[] = [$full, $half,$empty];
10.         }
11.     }
12. }

но на следующем шаге он не был акцептирован.

Option of packing barrels in one cart:

Barrels full: 0; half: 7; emty: 0
Barrels full: 1; half: 5; emty: 1
Barrels full: 2; half: 3; emty: 2
Barrels full: 3; half: 1; emty: 3

1. Method of packing barrels in three carts

cart: 1 Barrels full:1; half:5; empty:1;
cart: 2 Barrels full:3; half:1; empty:3;
cart: 3 Barrels full:3; half:1; empty:3;

2. Method of packing barrels in three carts
cart: 1 Barrels full:2; half:3; empty:2;
cart: 2 Barrels full:2; half:3; empty:2;
cart: 3 Barrels full:3; half:1; empty:3;

 

Почему противоречит? (7 + 7/2) / 3 = 3.5 на каждой телеге

 

Если на одну телегу положить 7 полубочек на ней будет 3.5
На две другие телеги останется 7 полных бочек на одну 4 на другую 3
На каждой телеге должно быть по 3.5

 

Не совсем понял задачу.

 

Простите, а что такое поровну Вы понимаете? Первую телегу Вы предложили занять 7 полубочками кваса.
Осталось на две телеги и 7 полных и 7 пустых бочек.
Поровну кваса на каждой телеге не получается с Вашим вариантом.
Теперь понятно? Или Вы меня разыгрываете?

 

Нет. Не совсем понял задачу.

 

Рассмотрим "похожую" задачу:
Сколькими различными способами можно погрузить на три грузовика
7 ящиков весом 1тонна,
7 ящиков весом 0.5 тонны
7 пустых ящиков весом 0 тонн?
В каждом грузовике должно быть по 7 ящиков и одинаковый вес груза.
Эта задача Вам понятна?

P. S. Это одна из практичисеих задач логистики: "Оптимальная загруза фуры заданого объём и грузоподъёмности.
Между прочим, именно блогадаря таким головомкам появилась область математики "Ленейное програмирование".

 

Точнее прочитал тз по диагонали. Тз решается комбинаторикой.
Прочитав нормально тз у меня нет проблем с решением данной задачи.

 

Значит условия задачи теперь Вам понятны. Очень интересно увидеть Ваше решение задачи .
--- Добавлено ---