All Questions
7
questions
18
votes
4
answers
7k
views
Looking to understand the rationale for money denomination
Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i d_i\quad\text{...
- 484
6
votes
5
answers
2k
views
Least wasteful use of stamps to achieve a given postage
You have sheets of $42$-cent stamps and
$29$-cent stamps, but you need at least
$\$3.20$ to mail a package. What is the
least amount you can make with the $42$-
and $29$-cent stamps that is ...
- 36.6k
9
votes
1
answer
5k
views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
user7055
4
votes
2
answers
2k
views
How do I prove a combinatorial statement about the change-making problem when using the greedy algorithm?
Let $D$ be set of denominations and $m$ the largest element of $D$. We say that $c$ is a counterexample if the greedy algorithm gives an answer different from the optimal one.
Now, apparently, if for ...
- 175
1
vote
2
answers
195
views
Finding the maximum value of elements to be selected in a grid - ZIO $2009$, P$1$
Hello Community! The above problem you see is a problem I got wrong. :( This is ZIO $2009$, P$1$.
I tried the problem and miserably found the wrong answer as $20$. Here is how my approach goes - part ...
- 779
1
vote
1
answer
87
views
An optimization problem to find the consecutive day subset with maximum value - ZIO $2006$, P$1$
Hello everybody! The above problem is a combinatorics problem I got wrong. :( This is ZIO $2006$, P$1$.
For the first part, I got as answer: $3$ which is wrong. What I did to try my value which I ...
- 779
0
votes
1
answer
79
views
Maximizing sum of metric function on a set (Adaptation of Hungarian Algorithm)
Suppose I have a set of unique elements $A=\{a_1, a_2, ..., a_n\}$. Suppose I also have a metric function $f:A\times A \rightarrow R^+$. I want to choose $k$ elements from $A$ (i.e. $a_{i_1},a_{i_2}, ....
- 2,457