UTS Programming Competition 2013 Problem 7
From ProgSoc Wiki
Problem 7: Cafe.10 Knapsack Special
A group of BScIT students have a couple of hours to spare before their next class. They're also a little bit peckish, so they'll head on down to their favourite Building 10 eatery, good old Cafe.10. When they arrive, they will check the contents of their wallets. Being archetypal "starving students", naturally they are skint. So they will pool their money together before approaching the counter, where kindly old lunchlady Joyce is waiting at the register, ready to take their order.
"Look, Joyce", says one of the gang, placing the money on the counter. "This is all we've got between us. Could you give us as many items from the menu as you can, with the total cost being the exact amount we have given you, please?"
Joyce is puzzled. "Why exactly?" she asks. "Why not slightly less? That way you can all have a little bit of money left over."
"No, it has to be exactly," another of the posse pipes up. "Because...umm...the girls in Bon Marche will beat us up if they know we have money on us...yeah..." Of course, he knows this to be false; everyone doing Media Arts -- boys and girls -- are all perfectly nice and friendly. But it was the first idea that came to mind, and hey, everyone believes that old "computer nerds are meek and defenseless" stereotype, right? What better way to elicit sympathy from the lunchlady than exploiting outdated societal myths?
Of course, Joyce doesn't buy their story for a second. Nevertheless, she is willing to entertain their eccentric demands. After all, Cafe.10 is a university cafe, and this sort of behaviour is to be expected from time to time. Besides, patronage seems to be rather low today. So Joyce picks up a menu and attempts to come up with an order. It's not long before she realises that this task is harder than it seems.
Noticing her frustration, another of the cohort offers to help Joyce. "Tell you what," he says. "Just give us a menu and we can write a little program on my laptop here that will tell us what to order and we'll get back to you."
"Sounds great," says Joyce, relieved. And not a moment too soon, as the lunchtime rush is about to begin...
Imagine you are one of the students and write the program as described.
You have prepared an input file based on the items of the menu and their respective prices, which are unique -- no two menu items cost the same.
The first line of input shall be a number (1 <= N <= 30) denoting the number of items on the menu. The subsequent N lines of input shall contain (in no particular order) a price, then, separated by a single space, the name of the menu item, which may contain alphabetic characters and spaces and shall be no longer than 30 characters in length. The final line of input shall be the amount of money you have all pooled for the order. All lines shall be terminated with the newline character.
Your output shall display, in price descending order, all of the items that make up your order as well as the number of times you intend to purchase an item, following the name of the item separated by a space. Note that you are able to order more than one of the same item from the menu. The final line of output shall display the total number of items ordered.
Note also that it is possible to come up with more than one selection of menu items for a given total price and menu. What you need to do is choose the selection that yields the greatest number of items. There will be at least one guaranteed solution.
6 2.15 Mixed Fruit 2.75 French Fries 3.35 Side Salad 3.55 Hot Wings 4.20 Mozzarella Sticks 5.80 Sampler Plate 15.05
2.15 Mixed Fruit 7 7
Put your solutions here!