- Posted by ehosca on January 30, 2008
The United States Postal Service currently sells stamps in the following denominations :
$0.01, $0.02, $0.03, $0.04, $0.05, $0.10, $0.24, $0.37, $0.39, $0.41, $0.48, $0.60, $0.63, $0.70,$0.75, $0.80, $0.83, $0.84, $0.87, $1.00, $3.85, $4.05, $4.60, $5.00, $14.40
James is preparing a small package to send out to his friend. The particular box that James has chosen has only enough room for 10 stamps after the address label is affixed.
What is the *minimum* amount of postage that cannot be placed on the box assuming James has an infinite number of stamps in each denomination ?
its : $89.96 withich would require 11 stamp from the given denominations ...
using System;
using System.Collections.Generic;
using System.Linq;
namespace PostOfficePuzzle
{
internal static class Program
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
private static void Main()
{
var denominations =
new List<int>{1,2,3,4,5,10,24,37,39,41,48,60,63,70,
75,80,83,84,87,100,385,405,460,500,1440};
// list of stamps
List<int> postage;
// list of list of stamps
var solutions = new List<List<int>>();
// init single stamp solutions
foreach (int i in denominations)
solutions.Add(new List<int>(new[] {i}));
for (int targetPostage = 0; targetPostage < int.MaxValue; targetPostage++)
{
postage = (from d in denominations
from s in solutions
where (d + s.Sum(i => i)).Equals(targetPostage)
orderby s.Count descending
select (new List<int>(new[] {d}.Concat(s)))).LastOrDefault();
if (postage != null)
{
solutions.Add(postage);
WritePostage(postage);
// exit condition
if (postage.Count > 10)
Console.ReadLine();
}
}
}
private static void WritePostage(List<int> postage)
{
string stampsList = string.Join(" , "
, postage.ConvertAll(s => string.Format("{0:C}"
, (double) s/100)).ToArray());
Console.WriteLine(string.Format("Postage = {0:C} Count = {1} Stamps = {2}"
, (double) postage.Sum(i => i)/100
, postage.Count
, stampsList));
}
}
}