[3922] Loiscenter | 2014-07-29 11:01:37 |
 Megjegyzés Erben Péter munkajaval kapcsolattal: 1)Nagyon tetszik nekem a algoritmus és egyenlőtlenség kombinácio alkalmazását. Sötszerintem általanos fejlesztéshez ezen az irányon érdemes menni. 2) köszönöm a Pataki J. munkahoz hozzáférhetöget. 3). szeretnek tovabb menni a khövetkezö iranyba: 2n (k.n)osszegu es egyenkent sulya nem nagyobb n-nel. Mi a legkisebb m szam hogy ket (k) egyenlö részre bonthatoság. ehhez tudtok -e irodalmat forrását segiteni nekem esetleg az tapasztalatokat, javaslatokat is!!! nagyon köszönöm szépen a segitségeteket!!!
Nguyen Van Loi.
|
Előzmény: [3920] Erben Péter, 2014-07-28 22:51:14 |
|
[3921] Loiscenter | 2014-07-29 10:46:16 |
 Elöbb szeretném folytatni a gondolataimat: Most tekintjük azt az esetet, amikor maximum csak 8 csoportra oszthato a számokat.legyen ezek A1, A2, A3,..., A8 növekvö összegü sorendben. A1,A2,...,A5 5-ösból kivalaszthato nehány tagot , melynek összege oszthato 25 -tel. ez csak 25 lehet ( mert 50-est kizarjuk, 75-est nem éri el azért mert utolso 2 tag összege nagyobb 25 -nél). 1)csak azt az esetet kell foglalkozni, amikor legalabb 3 tag van benne az 25-ösben.==> van 5-ös összegü tag. legyen ez A1=5. 2)Vesszük A2, A3,..., A6 -t , ebben megint talaljuk legalább 3 tagu 25-ös összeget. megint van 5-ös összegü tag. legyen ez A2=5. 3)Valasszuk ki A3, A4,..., A7. Ha ennek összege 75, akkor A8=15. A kompozicio:( 5, 5, 15, 15, 15, 15, 15, 15 ) ebböl 5+ 15+15+15=50 jo. Más különben megint van 5-ösöm. Legyen ez A3=5. 4) most vesszük A1, A2, A3,A7, A8. Ha összege 75 akkor A4+A5+ A6=25. ==> A4=5, ezért A7+A8=60, ebben csak 30+30 lehet. megint tudjuk 50-est kombinálni. 5)Hanem, akkor megint van 25-ös. tehat A4 = 5 vagy A4=10. 6)A felmaradó 3 tagbol egyik sem lehet 25, osszegük pedig legalább 75, kell hogy legyen. ezért van 30-nal nem kisebb tag ez legyen A8. igy vagy vele vagy masik ket taggal tudjuk kombinalni 50-est. kész.
|
Előzmény: [3920] Erben Péter, 2014-07-28 22:51:14 |
|
|
[3919] Erben Péter | 2014-07-28 22:33:54 |
 Ha &tex;\displaystyle k=1&xet;, akkor tehát az történt, hogy a 7 legnagyobb súlyt már be tudtuk pakolni, és az utolsó (&tex;\displaystyle b_1&xet;) nem fér egyik tartályba sem. Ebből következik, hogy &tex;\displaystyle b_1>1&xet;. Sőt, &tex;\displaystyle b_1=2&xet;, mert &tex;\displaystyle b_1\ge 3&xet;-ból az következne, hogy a súlyok összege legalább 24.
Továbbra is az összegre figyelve kiderül, hogy legalább 4 darab 2-es van. (&tex;\displaystyle 2+7\cdot 3 > 20&xet;, &tex;\displaystyle 2\cdot 2+ 6\cdot 3>20&xet;, stb.) Ha van 5 darab kettes, akkor kész vagyunk.
Ha pont 4 darab 2-es van, akkor a maradék 4 súly mind 3. Ebben az esetben &tex;\displaystyle 2+2+3+3&xet; megoldás.
Megjegyzés: A &tex;\displaystyle p(k)&xet; polinom általában is segít megtalálni egy olyan &tex;\displaystyle m&xet; számot, ami fölött mindig megy a kiválasztás. Amikor 100 az összeg, akkor az derül ki, hogy &tex;\displaystyle m=35&xet; a határ. (Ott is a &tex;\displaystyle k=1&xet; esettel kell külön megküzdeni.) &tex;\displaystyle m=34&xet;-re a 33 darab 3-as és 1 darab 1-es esetén nem állítható elő az 50.
|
Előzmény: [3918] Erben Péter, 2014-07-28 22:17:51 |
|
[3918] Erben Péter | 2014-07-28 22:17:51 |
 Megpróbálom leírni a kisebb feladatra, onnan lehet általánosítani.
Adott tehát 8 pozitív egész, összegük 20, egyik sem több, mint 10. Szeretnénk kiválasztani közülük néhányat, amelyek összege 10.
Megadunk egy algoritmust, ami sok esetben megadja a megoldást. Ha mégsem, azokkal az esetekkel elbánunk valahogy.
Algoritmus: A számokat súlyoknak tekintjük, amiket két 10 kg kapacitású "tartályba" próbálunk bepakolni a következő módon. Súly szerint csökkenő sorrendben haladunk, és a soron következő súlyt berakjuk valamelyik tartályba, ahova még elfér. Soha nem lépjük át a 10 kg-os határt. Ha végigmegy az algoritmus, akkor örülünk. Ha nem, akkor megvizsgáljuk, hol akadtunk el.
Az elakadás szükséges feltétele: Legyenek a súlyok: &tex;\displaystyle b_8\ge b_7 \ge \dots \ge b_1&xet;. Tegyük fel, hogy a &tex;\displaystyle k&xet;. súly az első, amit már egyik tartályba sem tudunk berakni. Ha a tartályokban pillanatnyilag megmaradt szabad kapacitás &tex;\displaystyle h_1&xet; és &tex;\displaystyle h_2&xet;, akkor az elakadás azt jelenti, hogy &tex;\displaystyle b_k>h_1&xet; és &tex;\displaystyle b_k>h_2&xet;. Egészekrők van szó, vagyis &tex;\displaystyle b_k\ge h_1+1&xet; és &tex;\displaystyle b_k\ge h_2&xet;.
Most felhasználjuk, hogy a szabad kapacitások összege pontosan a még be nem pakolt súlyok összege.
&tex;\displaystyle 2b_k\ge h_1+ h_2 +2 = b_1+b_2+\dots+b_{k-1}+b_k+2 \rightarrow
b_k \ge b_1+b_2+\dots+b_{k-1}+2 \ge k+1&xet;
Alulról becsülve az összes súly összegét:
&tex;\displaystyle 20=b_1+b_2+\dots+b_8 = (b_1+\dots+b_{k-1})+(b_k+\dots+b_8)\ge k-1+(8-k+1)\cdot(k+1)&xet;
Rendezés után &tex;\displaystyle k^2-9k+12\ge 0&xet; adódik. Csak olyan &tex;\displaystyle k&xet; indexű súlynál akadhat el az algoritmus, amire a &tex;\displaystyle p(k)=k^2-9k+12&xet; polinom nemnegatív. Az fog kiderülni, hogy nem sok ilyen &tex;\displaystyle k&xet; van.
A &tex;\displaystyle p(k)&xet; csak &tex;\displaystyle k=1&xet; és &tex;\displaystyle k=8&xet; esetén nemnegatív, a minket érdeklő halmazon.
&tex;\displaystyle k=8&xet; nem lehetséges, mert feltettük, hogy minden súly legfeljebb 10. Marad tehát a &tex;\displaystyle k=1&xet; eset, ott még kell egy kicsit dolgozni. (Folyt. köv.)
|
Előzmény: [3917] csábos, 2014-07-28 21:28:13 |
|
|
[3916] Erben Péter | 2014-07-28 19:42:26 |
 Innen már tényleg kevés van hátra.
A 8 tag esete az eredeti probléma kisebb változata. Legyenek a &tex;\displaystyle b_1, b_2,\dots,b_8&xet; a tagokban lévő számok összegének ötödével egyenlők. Így &tex;\displaystyle b_1+b_2+\dots+b_8=20&xet;, és &tex;\displaystyle b_i\le 10&xet;. Megmutatható, hogy kiválasztható közülük néhány, amelyek összege 10. A kiválasztott &tex;\displaystyle b_i&xet;-k megadják az eredeti feladat megoldását: a nekik megfelelő tagokban lévő számok összege 50.
|
Előzmény: [3915] Loiscenter, 2014-07-28 15:23:48 |
|
[3915] Loiscenter | 2014-07-28 15:23:48 |
 Nagyon jo ötletet meritettem a hozzászólásotokböl.
Most tekintjuk azt legfinomabb felosztást, melyre csak 7 csoport a maximális. 1) csoportok közti szamok különbsége oszthato 5-tel. 2) (LEGFONTOSABB): csorton belül szamok különbsége is rendelkezik ezzel a tulajdonsaggal.( különben csinálhatjuk egy rossz cserét). összegezve : 35 számokbol bármelyik kettönek különbsége osztható 5-tel. 3)vannak 3-nal kisebb szám. tehat vagy 1, vagy 2( és kizárják egymást). a)ha legkisebb szám 2. akkor alap 2.35=70. ezért mar csak legfeljebb(30:5)=6 darab 7-nal nem kisebb szam lehet. azaz legalább (35-6)=29 darabb 2-es van ==> kivalasztható 25-öt , kész.(ez pont Erben P. esete) b) ha legkisebb szam 1-es. akkor alap: 35. csak (65:5=13 darab 6-nál nem kisebb. azaz (35-13)=22 darab 1-es van legalabb. tehat van 4 csoport , melynek összege 5 ( összesen 20) és 3 csoport, melynek összege 80.téhát van 30-nal nagyobb összegü. ennek összege csak 50-nal nagyobb lehet:55,60,65,70.(mert van még két csoport).ebbol a csoportbol 2 darabb legnagyobb szam kicerélem a legkiebb-be igy csokkenthetjuk 50 alá az összeget. Tovább kiegészithetem 1-essekkel 50-re. téhat a 7-es csoport esete el van intézve. csak 8-as csoport esete maradt. (de jo !!!!)
|
Előzmény: [3914] csábos, 2014-07-28 10:51:42 |
|
[3914] csábos | 2014-07-28 10:51:42 |
 A csoportok közti csere azt jelenti, hogy ha pontosan 5 elemből áll egy csoport, és van két ilyen is, akkor egy-egy elemet cserélve újabb 5-ösöket kapunk, amelyekből szintén kiválasztható néhány szám. amely összege osztható 5-tel. Ha a cserélt számok nem kongruensek egymással modulo 5, akkor kisebb csoportokat kapunk. Így feltehető, hogy ha van több 5-ös csoport, akkor az összes azokban lévő elem páronként kongruens modulo 5.
|
Előzmény: [3913] Erben Péter, 2014-07-28 07:24:17 |
|
[3913] Erben Péter | 2014-07-28 07:24:17 |
 A 3. pontot nem értem, amikor cserélünk számokat a tagok között. Pedig arra biztosan szükség lesz, amint a következő példa mutatja.
Tegyük fel, hogy a 35 szám így néz ki: 29 darab 2-es és 6 darab 7-es. Ekkor a 7-est tartalmazó tagok pontosan öt eleműek, és a csupa 2-esből állók is. Vagyis pontosan 7 tag lesz.
Előfordulhat, hogy a 7 tag így néz ki: 6-szor: (2+2+2+2+7), 1-szer: (2+2+2+2+2). Itt a tagok összegének megváltoztatása nélkül nem tudjuk az ötvenet előállítani, hiszen van 6 db 15-ös és 1 db 10-es.
|
Előzmény: [3912] Loiscenter, 2014-07-27 16:05:40 |
|