Skip to content

Instantly share code, notes, and snippets.

@kloneets

kloneets/gist:69e75dbb0c2f979d98fe

Created May 27, 2015 05:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kloneets/69e75dbb0c2f979d98fe to your computer and use it in GitHub Desktop.
Save kloneets/69e75dbb0c2f979d98fe to your computer and use it in GitHub Desktop.
Download ZIP
Mazākais iespējamais pārpalikums
Raw
gistfile1.txt
Problēmas apraksts: ir doti random skaits vienāda veida kvadrāti. Šos kvadrātus jāsakārto taisnstūra laukumā tā, lai būtu aizpildīts pilns taisnstūris un pāri paliktu pēc iespējas mazāk kvadrātu. Maksimālais X un Y dimensiju lielums ir 200 kvadrāti katrā dimensijā.
Piemērs:
Pieņemsim, ka max X un Y lielums ir 6.
Ir doti 10 kvadrāti.
Labākais sakārtošanas vieds būtu 5 kvadrāti pa vienu asi un 2 kvadrāti pa otru (pārpalikuma nav).
Ja liks pilnu 6x2, tad pāri paliks 4 kvadrāti. Ja liks 4x2, tad pāri palis 2 kvadrāti un līdzīgi.
Risinājums: vajadzētu daudz maz optimālu algoritmu, lai noteiktu vajadzīgās dimensijas, atmetot pēc iespējas mazāk kvadrātus.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment