[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
predmeti vo kutii  XML
Forum Index » Други задачи
Author Message
OP Magic Potato


[Avatar]

Joined: 16/03/2011 21:20:03
Messages: 62
Offline

Mi treba pomosh so zadacava, pozelno bi mi bilo nekoj da mi ja reshi i da mi dade objasnuvanje

Dadeni se M kutii, site so ista golemina (golemina G) i N predmeti. Napishi programa koja ke kaze dali moze site predmeti da se smestat vo kutiite. Eden predmet ne moze da se podeli vo dve kutii.

Ex:
input:
8 4 15 // N, M, G (1<=N,M,G<=20)
7 8 6 9 5 10 4 11 // N-te predmeti

output:
1 // 1 ako moze da se smestat predmetite u kutiite, 0 ako ne moze da se smestat

input:
4 2 15
16 1 1 1

output:
0

p.s ne mi treba brute force reshenie, i greedy ne pominuva

p.p.s. ova ne e oficijalna zadaca, jas ja napraviv(ako vekje postoi vakov problem stavete link od Wikipedia ). Mi treba reshenieto na zadacava za da mozam da go iskoristam kako alatka vo edna zadaca od USACO(zadacata "Raucous Rockers", 3.4.4)
[Email] [MSN]
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Зошто не поминува greedy? Или не сфаќам што прашуваш, или нема никаков проблем со greedy-то.
filip_bujaroski


[Avatar]

Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline

obi1kenobi wrote:Зошто не поминува greedy? Или не сфаќам што прашуваш, или нема никаков проблем со greedy-то.


Se soglasuvam so Obi
Greedy raboti

Duri mislam deka imase vakva zadaca na treningot na mendo

This message was edited 1 time. Last update was at 13/04/2012 11:12:50


Live to play, die for fun.
[Email] [MSN]
OP Magic Potato


[Avatar]

Joined: 16/03/2011 21:20:03
Messages: 62
Offline

obi1kenobi wrote:Зошто не поминува greedy? Или не сфаќам што прашуваш, или нема никаков проблем со greedy-то.


**ne go opishav inputot dobro, vo prviot red se dadeni 3 integers N(brojot na predmeti), M(brojot na kutii) i G(volumenot na site kutii posebno), a vo vtoriot red se dadeni N integers, broevi koi gi opishuvaat volumenite na predmetite.

jas mislam na vakvo greedy: gi sortirash predmetite po rastecki redosled, i polnish edna kutija se dodeka sobira(prvo go stavsh prviot element, pa vtoriot, pa tretiot se dodeka moze kutijata da sobere). koga ke go nadminesh kapacitetot na prvata kutija, probuvash da ja napolnish vtorata kutija itn. Ova go povtoruvash se dodeka ima mesto vo kutiite za sledniot predmet, ili go povtoruvash se dodeka ima predmeti za stavanje. Na kraj, ako si gi iskoristil site elementi pecatish 1(moze elementite da se smestat vo kutiite), vo sprotivno pecatish 0.

ova reshenie ne e tocno, kontra primer e
N: 8 // dadeni se 8 predmeti
M: 4 // dadeni se 4 kutii
G: 15 // prvata kutija ima volumen 15, vtorata 15, tretata 15 i cetvrtata kutija ima volumen 15.
N-te predmeti: 7 8 6 9 5 10 4 11 // predmetite se so vloumen: 7, 8, 6, 9, 5, 10, 11;

greedyto vaka ke raboti:
ja sortira nizata: 4 5 6 7 8 9 10 11
i gi stava predmetite:
vo prvata kutija ke gi stavi predmetite so V = 4 5 6
vo vtorata kutija ke gi stavi predmetite so V = 7 8
vo tretata kutija ke gi stavi predmetie so V=9 (samo eden predmet, bidejki sledniot e so V=10 i nema da go sobere vo preostanatiot prostor)
vo cetvrtata kutija ke go stavi predmetite so V=10
ke ostane predmetot so V=11, odnosno programa ke vrati 0 bidejki ne usteala da gi smesti site predmeti vo kutiite

tocniot rezultat e 1
vo prvata kutija da vlezat predmetite so V=7 8
vo vtorata kutija da vlezat predmetite so V=6 9
vo tretata kutija da vlezat predmetite so V=5 10
vo cetvrtata kutija da vlezat predmetite so V=4 11
bidejki site predmeti se iskoristeni tocnoto reshenie e 1(predmetite mozat da se smestat vo kutiite)
[Email] [MSN]
bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

А пробај со вакво динамичко. Гледаш во која кутија можеш најмногу предмети да ставиш, па ги вадиш предметите што си ги искористил и продолжуваш за сите кутии, ако ти останале елементи испечати 0, ако не испечати 1. Ова е knapsack проблем како што гледам..
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.

This message was edited 1 time. Last update was at 13/04/2012 16:03:30

OP Magic Potato


[Avatar]

Joined: 16/03/2011 21:20:03
Messages: 62
Offline

bedzo wrote:А пробај со вакво динамичко. Гледаш во која кутија можеш најмногу предмети да ставиш, па ги вадиш предметите што си ги искористил и продолжуваш за сите кутии, ако ти останале елементи испечати 0, ако не испечати 1. Ова е knapsack проблем како што гледам..

ne te razbiram so sakash da pravish, a inache site kutii imaat ist kapacitet.

obi1kenobi wrote:Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.


go razmisliv ova reshenie, ama nema da mi pomogne deka DFS-to ke treba da go povtoruvam 2^N pati (najlosh slucaj N=20,slozenosta O((2^20)*DFS))
[Email] [MSN]
bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

obi1kenobi wrote:Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.

Зошто да не работи? M^2*(М/2)*N сложеност. Поточно ќе го разделиш на М ранец-проблеми и ќе гледаш колку можеш повеќе предмети да ставиш во еден ранец, и потоа ранецот со најмногу ставени предмети ќе го тргнеш (бидејќи ништо неможе да се става во него веќе) и ќе ги извадиш предметите што си ги ставил во ранецот кој ти е најмногу пополнет.

This message was edited 1 time. Last update was at 13/04/2012 18:38:26

bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

Еве го средив ова, мислам дека е точно, а изгледа може и уште да се упрости.
N^2*G

This message was edited 1 time. Last update was at 13/04/2012 18:36:22

obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

bedzo wrote:
obi1kenobi wrote:Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.

Зошто да не работи? M^2*(М/2)*N сложеност. Поточно ќе го разделиш на М ранец-проблеми и ќе гледаш колку можеш повеќе предмети да ставиш во еден ранец, и потоа ранецот со најмногу ставени предмети ќе го тргнеш (бидејќи ништо неможе да се става во него веќе) и ќе ги извадиш предметите што си ги ставил во ранецот кој ти е најмногу пополнет.


Кои предмети ќе ги ставиш во кој ранец? Како знаеш дека баш тие предмети што си ги ставил прават оптимално решение? Ај дај напиши (псеудо)код да ти дадам контра-пример.
bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

Razmisluvav na toa pa mi izleze deka mojata idea e greedy so dinamicko, eve kako ke odi:

Gi pominuvame site kutii i za sekoja kutija go pustame dinamickoto sto go postirav pogore, pa kje ja najdeme kutijata koja sme ja ispolnile najmnogu i gi briseme predmetite sto sme gi stavile, ja briseme kutijata i prodolzuvame istoto so ostanatite kutii.
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

bedzo wrote:Razmisluvav na toa pa mi izleze deka mojata idea e greedy so dinamicko, eve kako ke odi:

Gi pominuvame site kutii i za sekoja kutija go pustame dinamickoto sto go postirav pogore, pa kje ja najdeme kutijata koja sme ja ispolnile najmnogu i gi briseme predmetite sto sme gi stavile, ja briseme kutijata i prodolzuvame istoto so ostanatite kutii.


greedy со динамичко, тоа треба во signature да си го ставиш, ако не и во алманах да ти го напишат

Ај вака. Имаш кутии што берат 6, 4 и 2, и имаш предмети што тежат 4, 3, 3, 2. Како со твоето динамичко ќе гарантираш дека 3 и 3 ќе завршат во кутијата со големина 6, а не 4 и 2? Ќе ги провериш двата случаи? Ако ги проверуваш двата случаи, тогаш сложеноста на решението е експоненцијална затоа што истава конфигурација ќе ја повторам n пати и ќе мораш сите пермутации да ги испробаш, а ако не ги проверуваш тогаш ова е контра-пример.
bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

Ништо, лоша ми била идеата :Р
filip_bujaroski


[Avatar]

Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline

obi1kenobi wrote:
bedzo wrote:Razmisluvav na toa pa mi izleze deka mojata idea e greedy so dinamicko, eve kako ke odi:

Gi pominuvame site kutii i za sekoja kutija go pustame dinamickoto sto go postirav pogore, pa kje ja najdeme kutijata koja sme ja ispolnile najmnogu i gi briseme predmetite sto sme gi stavile, ja briseme kutijata i prodolzuvame istoto so ostanatite kutii.


greedy со динамичко, тоа треба во signature да си го ставиш, ако не и во алманах да ти го напишат

Ај вака. Имаш кутии што берат 6, 4 и 2, и имаш предмети што тежат 4, 3, 3, 2. Како со твоето динамичко ќе гарантираш дека 3 и 3 ќе завршат во кутијата со големина 6, а не 4 и 2? Ќе ги провериш двата случаи? Ако ги проверуваш двата случаи, тогаш сложеноста на решението е експоненцијална затоа што истава конфигурација ќе ја повторам n пати и ќе мораш сите пермутации да ги испробаш, а ако не ги проверуваш тогаш ова е контра-пример.


Mi se chini deka Kompirot spomna deka site kutii se so ista golemina

Live to play, die for fun.
[Email] [MSN]
bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

^ Разгледувавме во различни кутии сега. А инаку за со исти кутии го оставив кодот погоре.
 
Forum Index » Други задачи
Go to:   
Powered by JForum 2.1.8 © JForum Team