Author |
Message |
|
^ А што ќе ти е тешко ако кликнеш 2 клика повеќе?
|
 |
|
Ова да не ти е вишок? 38ми ред.
readln;
|
 |
|
@ob1kenobi
А да почнуваме прво да ги полниме најмалите кутии? Така ќе бидеме сигурни за овој контра-тест пример.
|
 |
|
^ Разгледувавме во различни кутии сега. А инаку за со исти кутии го оставив кодот погоре.
|
 |
|
Ништо, лоша ми била идеата :Р
|
 |
|
http://www.cs.org.mk/index.php/natprevari/srednoob...egionalennatprevar/2-razno/122
|
 |
|
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.
|
 |
|
Еве го средив ова, мислам дека е точно, а изгледа може и уште да се упрости. N^2*G
|
 |
|
obi1kenobi wrote:Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред. EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.
Зошто да не работи? M^2*(М/2)*N сложеност. Поточно ќе го разделиш на М ранец-проблеми и ќе гледаш колку можеш повеќе предмети да ставиш во еден ранец, и потоа ранецот со најмногу ставени предмети ќе го тргнеш (бидејќи ништо неможе да се става во него веќе) и ќе ги извадиш предметите што си ги ставил во ранецот кој ти е најмногу пополнет.
|
 |
|
А пробај со вакво динамичко. Гледаш во која кутија можеш најмногу предмети да ставиш, па ги вадиш предметите што си ги искористил и продолжуваш за сите кутии, ако ти останале елементи испечати 0, ако не испечати 1. Ова е knapsack проблем како што гледам..
|
 |
|
Го поедноставив кодот и ја решив. Климент ако ти треба некоја помош кажи.
|
 |
|
Ау епа по се изгледа треба 2 пати да пуштам динамичко. Еднач само за множење и еднач само за одзимање. Така множењето ќе има предност.
|
 |
|
11*11+111+1+1+1+1+1+1+1+1+1
Ova vrakja pomalku od 36
|
 |
|
Еве како ти го средив за во стринг да ти го стави.
|
 |
|
filip_bujaroski wrote:
bedzo wrote:8 од интернационални е исто така многу лесна.
Aj daj mi hint nekoj za dinamickoto na taa?
Stvarno ne mi teknuva nishto od pocetok 
низа dp[n][2]
dp[i][0] ти означува ако го земеш и-тиот правоаголник вертикално
dp[i][1] ти означува ако го земеш хоризонтално
и ќе ги пополнуваш по тоа што ќе земеш некое од предходниот ред, за да го максимизираш резултатот со i правоаголници.
|
 |
|