Minimalny rozkład

Nowax · Post autor: **Nowax** » 9 maja 2011, o 19:40

Witam,

Chciałbym się poradzić jak rozłożyć liczbę przy użyciu minimalnej ilość liczb.
Dokładnie chodzi mi o coś takiego że mam zbiór \(\displaystyle{ A = \{1, 2, 3, 4, 50, 100, 57\}}\) i chcę rozłożyć liczbę \(\displaystyle{ 5478}\) przy jak najmniejszym wykorzystaniu elementów ze zbioru \(\displaystyle{ A}\)

Ciamolek · Post autor: **Ciamolek** » 9 maja 2011, o 20:24

\(\displaystyle{ 52 \cdot 100 + 4 \cdot 57 + 1 \cdot 50}\)

Nowax · Post autor: **Nowax** » 9 maja 2011, o 22:07

Wybacz @Afis postaram się zastosować do tego.

Ciamolek pisze:Ciamolek

Metodą prób i błędów dochodzę do tego ale chodzi mi o to czy nie ma jakiegoś szybkiego sposobu określenia ponieważ mi to trochę zajmuje

Ciamolek · Post autor: **Ciamolek** » 9 maja 2011, o 23:36

Nie przychodzi mi na myśl jakiś konkretny algorytm... ale metodą prób i błędów w tym przypadku wychodzi dość szybko.

Wiesz, że małych liczb chcesz uniknąć. Ponadto wiesz, że użyć więcej niż jeden raz liczbę 50 jest bez sensu, bo wówczas za dwie liczby 50, możesz wstawić setkę. Zatem dostaje Ci to relatywnie niewiele możliwości: wstawiaj jak najwięcej setek, kilka 57 i maksymalnie jedną 50 i działa.