Комбинаторна задача за камиони и сандъци

[ToZero]

Това е една стара задача, на която не знам решението.

Общото тегло на някакъв брой сандъци е 13,5 тона. Всеки сандък тежи не повече от 350 кг. Един камион може да бъде натоварен най-много с 1,5 тона. Да се покаже, че 11 камиона са достатъчни да поемат всички сандъци.

[Гост]

Камиони и сандъци-page-001.jpg (203.81 KiB) Прегледано 235 пъти

[Гост]

Камиони и сандъци 2-page-001.jpg (333.37 KiB) Прегледано 192 пъти

Камиони и сандъци 2-page-002.jpg (231.41 KiB) Прегледано 192 пъти

[ptj]

1.) Възможно е да се докаже, че "най-лошите" случаи се получават когато всички сандъци са с еднакво тегло.

2.)Ако всички сандъци са [tex]11n+k[/tex] и с еднакво тегло , [tex]n[/tex] и [tex]k[/tex] са естествени, а [tex]k<11[/tex], то :

При [tex]k \ge 4[/tex] максимума на [tex](n+1) \frac{13500}{11n+k}[/tex] e 1500 и се достига за [tex]k=4[/tex] и [tex]n=1[/tex], (т.е. при 45 сандъка).

3.) При [tex]к=3[/tex] ограничението за максимално тегло на всеки сандък дава не по-малко от 39 сандъка, но тогава теглото на всеки 4 сандъка е по-малко от 1500.

Изпълнението на 1),2) и 3.) гарантира, че всички сандъци могат дасе качат на 11 камиона.

[pal702004]

1.) Възможно е да се докаже, че "най-лошите" случаи се получават когато всички сандъци са с еднакво тегло.

Това е всъщност един от най-добрите случаи. (Особено 45 сандъка по 300 кг, тогава са достатъчни 9 камиона). Лош е когато са 44 сандъка са с тегло 300 кг плюс един водороден атом и един сандък с тегло 300 кг. минус 44 водородни атома.

[peyo]

Това е една стара задача, на която не знам решението.

Общото тегло на някакъв брой сандъци е 13,5 тона. Всеки сандък тежи не повече от 350 кг. Един камион може да бъде натоварен най-много с 1,5 тона. Да се покаже, че 11 камиона са достатъчни да поемат всички сандъци.

Възможно най-неефективното натоварване ще е когато пропуснатата полза за всеки камион е най-голяма и тя е 349 кг. за камион. Значи:

1500 - 349 = 1151 кг. товар на камион
13500/1151= 11.729 камиона

И може би работим с камиони, които могат само да са цели числа, то ще ни трябват 12 такива.
(11 камиона и един пикат също може да ни свършат работа)

[pal702004]

Решението на гост е правилното. Наистина разковничето е, че можем да натоварим на един камион повече от 1200 кг. (ако трябва). Товарим сандъците последователно от най-тежкия към най лекия. Да предположим, че на някой камион сме натоварили $t<1200$ и не можем да натоварим повече. ($1150$ със сигурност можем) Това е възможно, само ако всички останали са по-тежки от 300 кг. Но тогава и тези, които вече сме натоварили в камиона са по-тежки от 300. При тези условия те са точно 4 на брой и общото им тегло е между $4\cdot 300$ и $4\cdot 350$ - противоречие. Така че със сигурност в 10 камиона можем да натоварим поне 12000 кг, а в единадесетия - каквото остане.