public class ShoppingSpreeCombinations
1: //ShoppingSpreeCombinations.java
3: import java.util.ArrayList;
5: public class ShoppingSpreeCombinations
6: {
7: // Max number of items in shopping bag
8: public static final int MAX_SHOPPING_BAG_SIZE = 3;
10: /* Output every combination of items that fit
11: in a shopping bag. Each recursive call moves
12: one item into the shopping bag.
13: */
14: public static void shoppingBagCombinations
15: (
16: ArrayList<GroceryItem> currBag, // Bag contents
17: ArrayList<GroceryItem> remainingItems // Available items
18: )
19: {
20: int bagValue; // Cost of items in shopping bag
21: GroceryItem tmpGroceryItem; // Grocery item to add to bag
22: int i; // Loop index
24: // Base case: Shopping bag full
25: if (currBag.size() == MAX_SHOPPING_BAG_SIZE)
26: {
27: bagValue = 0;
28: for (i = 0; i < currBag.size(); ++i)
29: {
30: bagValue += currBag.get(i).priceDollars;
31: System.out.print(currBag.get(i).itemName + " ");
32: }
33: System.out.println("= $" + bagValue);
34: }
35: else // Recursive case: move one
36: {
37: for (i = 0; i < remainingItems.size(); ++i) // item to bag
38: {
39: // Move item into bag
40: tmpGroceryItem = remainingItems.get(i);
41: remainingItems.remove(i);
42: currBag.add(tmpGroceryItem);
44: shoppingBagCombinations(currBag, remainingItems);
46: // Take item out of bag
47: remainingItems.add(i, tmpGroceryItem);
48: currBag.remove(currBag.size() - 1);
49: }
50: }
51: }
53: public static void main(String[] args)
54: {
55: ArrayList<GroceryItem> possibleItems = new
56: ArrayList<GroceryItem>(); // Possible shopping items
57: ArrayList<GroceryItem> shoppingBag = new
58: ArrayList<GroceryItem>(); // Current shopping bag
59: GroceryItem
60: tmpGroceryItem; // Temp item
62: // Populate grocery with different items
63: tmpGroceryItem = new GroceryItem();
64: tmpGroceryItem.itemName = "Milk";
65: tmpGroceryItem.priceDollars = 2;
66: possibleItems.add(tmpGroceryItem);
68: tmpGroceryItem = new GroceryItem();
69: tmpGroceryItem.itemName = "Belt";
70: tmpGroceryItem.priceDollars = 24;
71: possibleItems.add(tmpGroceryItem);
73: tmpGroceryItem = new GroceryItem();
74: tmpGroceryItem.itemName = "Toys";
75: tmpGroceryItem.priceDollars = 19;
76: possibleItems.add(tmpGroceryItem);
78: tmpGroceryItem = new GroceryItem();
79: tmpGroceryItem.itemName = "Cups";
80: tmpGroceryItem.priceDollars = 12;
81: possibleItems.add(tmpGroceryItem);
83: // Try different combinations of three items
84: shoppingBagCombinations(shoppingBag, possibleItems);
85: }
86: }