Using Recursion to Generate a List of Items You Can Afford on a Budget

Question

Recursion is still baffling me. I understand the basis of it and how it's supposed to work, but I am struggling with how to actually make it work. For my function, I'm given a cell array that has costume items and prices, as well as a budget (given as a double). I have to output a cell array of the items I can buy (in order from cheapest to most expensive) and output how much money I have leftover in my budget. There is a chance I will run out of money before I buy all of the items I need to, and a chance where I do buy everything I need. These would be my two terminating conditions. I have to use recursion and I am not allowed to use sort in this problem. So I am struggling a little. Mostly with figuring out the base case situation. I don't understand that bit. Or how to do recursion with two inputs and outputs. So basically my function looks like:

function[bought, money] = costumeParty(items, budget)

Here is what I have to output:

Test case:

 Costume Items:
'Eyepatch'  8.94000000000000
'Adult-sized Teletubby Onesie'  2.89000000000000
'Cowboy Boots'  1.30000000000000
'Mermaid Tail'  1.75000000000000
'Life Vest' 8.10000000000000
'White Bedsheet With Eyeholes'  4.30000000000000
'Lizard Leggings'   0.650000000000000
'Gandalf Beard' 4.23000000000000
'Parachute Pants'   7.49000000000000
'Ballerina Tutu'    8.75000000000000
'Feather Boa'   1.69000000000000
'Groucho Glasses'   6.74000000000000
'80''s Leg Warmers' 5.08000000000000
'Cat Ear Headband'  6.36000000000000
'Ghostface Mask'    1.83000000000000
'Indoor Sunglasses' 2.25000000000000
'Vampire Fangs' 0.620000000000000
'Batman Utility Belt'   7.08000000000000
'Fairy Wand'    5.48000000000000
'Katana'    6.81000000000000
'Blue Body Paint'   5.70000000000000
'Superman Cape' 4.78000000000000
'Assorted Glow Sticks'  4.07000000000000
'Ash Ketchum''s Baseball Cap'   3.57000000000000
'Hipster Mustache'  6.47000000000000
'Camouflage Jacket' 8.73000000000000
'Two Chains Value Pack' 4.76000000000000
'Toy Pistol'    8.41000000000000
'Sushi Chef Headband'   2.59000000000000
'Pitchfork' 8.57000000000000
'Witch Hat' 4.27000000000000
'Dora''s Backpack'  4.13000000000000
'Fingerless Gloves' 0.270000000000000
'George Washington Wig' 7.35000000000000
'Clip-on Parrot'    4.32000000000000
'Christmas Stockings'   8.69000000000000

A lot of items sorry.

[costume1, leftover1] = costumeParty(costumeItems, 5);
     costume1 => {'Fingerless Gloves'
                  'Vampire Fangs'
                  'Lizard Leggings'
                  'Cowboy Boots'
                  'Feather Boa'      }
     leftover1 => 0.47

What I have:

function[bought, money] = costumeParty(items, budget)
%// I commented these out, because I was unsure of using them:
%// item = [items(:,1)];
%// costumes = [item{:,:}];
%// price = [items{:,2}];

   if budget == 0 %// One of the terminating conditions. I think.
    money = budget;
    bought ={};
%// Here is where I run into issues. I am trying to use recursion to find out the money leftover
else 
    money = costumeParty(items{:,2}) - costumeParty(budget); 
%// My logic here was, costumeParty takes the second column of items and subtracts it from the budget, but it claims I have too many inputs. Any suggestions?
    bought = {items(1,:)};
end

end

If I could get an example of how to do recursion with two inputs/outputs, that'd be great, but I couldn't seem to find any. Googling did not help. I'm just...baffled.

I did try to do something like this:

function[bought, money] = costumeParty(items, budget)
item = [items(:,1)];
costumes = [item{:,:}];
price = [items{:,2}];

if budget == 0
    money = 0;
    bought ={};

else 
    money = price - budget;
    bought = {items(1,:)};
end

 end

Unfortunately, that's not exactly recursive. Or, I don't think it is and that didn't really work anyway. One of the tricks to doing recursion is pretending the function is already doing what you want it to do (without you actually coding it in), but how does that work with two inputs and outputs?

Another attempt, because I'm going to figure this darn thing out somehow:

function[bought, money] = costumeParty(items, budget)

price = [items{:,2}]; %// Gives me the prices in a 1x36 double

if price <= budget %// If the price is less than the budget (which my function should calculate) you populate the list with these items
    bought = [costumeParty(items,budget)];
else %// if not, keep going until you run out of budget money. Or something
    bought = [costumeParty(items{:,2},budget)];
end

I think I need to figure out how to sort the prices first. Without using the sort function. I might just need a whole lesson on recursion. This stuff confuses me. I don't think it should be this hard .-.

I think I'm getting closer!

  function[bought, money] = costumeParty(items, budget)

%My terminating conditions are when I run out of the budget and when buying
%the next item, would break my budget
price = [items{:,2}];
Costumes = [items(:,1)];
[~,c] = size(price);
bought = {};
Locate = [];
List = [];
for j = 1:c %// Need to figure out what to do with this
    [Value, IND] = min(price(:));
    List = [List price(IND)]; 
end

while budget >= 0
        if Value < budget
        bought = {Costumes(IND)};
        money = budget - price(IND);
    elseif length(Costumes) == length(items)
        bought = {Costumes(IND)};
        money = budget - price(IND);
    else
        bought=43; %// Arbitrary, ignore
        budget = budget - price;
    end
    budget = budget - price;
end
duck = 32; %// Arbitrary, ignore

I need to know how any adult-sized Teletubbie costumes I can buy haha — Jessica Marie, Oct 30 '14 at 21:34
There is a question that discusses how to solve this in java: http://stackoverflow.com/questions/7774769/how-do-i-solve-the-classic-knapsack-algorithm-recursively this easy translates to matlab. — bdecaf, Oct 31 '14 at 01:02
I barely understand it explained in MATLAB. I doubt having it explained in Java is going to be any help. Thanks though. — Jessica Marie, Oct 31 '14 at 01:03
@bdecaf Yep. I was right. I looked at it, that is not translatable to me. I looked at all of the options too. Not happening. Not at the level of programming I'm at. — Jessica Marie, Oct 31 '14 at 01:12
Don't be discouraged so easily. All you need is to adjust both inputs for the next call. And do not use the sort idea this will give wrong results you need to consider every option. — bdecaf, Oct 31 '14 at 01:33
That doesn't make sense to me. I tried to translate the problem. I just got more confused. I don't understand recursion. Or coding. Or Java. Or MATLAB. — Jessica Marie, Oct 31 '14 at 01:34

BioSP · Answer 1 · 2014-10-30T22:00:31.377

From my understanding of the question the recursion needs to be used for sorting the items arrays and then after you have a sorted array you can then decide how many objects and which can be bought based on the budget you have

Therefore, you need to implement a classic recursive sorting algorithm. You may find a few online but the idea is to split your whole list into sub lists and do the same sorting for them and so on.

After the implementation, you will then need to have a threshold of the budget in place.

Another approach will be as you started with 2 items. Then you will need to scan the whole list every time in the look for the cheapest item, cross it from the list and pass the next function an item list with this item missing and a budget that will be lower by that some. Though I don't see the need of a recursion for this implementation, since loops will be more then enough here.

Edit: Code:

This is an idea of a code, didn't run it, and it should have problems with the indexing (you nedd to address the budget and the lables differently) but I think it shows the point.

function main(items,budget)
     boughtItemIndex=itemslist(items,budget)
     moneyLeft=budget;
     for i=1:1:length(boughtItemIndex)
       disp(item(boughtItemIndex(i)))
       moneyLeft=moneyLeft-boughtItemIndex(i);
     end
     disp('Money left:');
     moneyLeft;   

boughtItemIndex=function itemslist(items,budget)
 [minVal minInd]=findmin(items)
 if (budget>minVal)
       newitems=items;
       newitem(minInd)=[];
       newbudget=budget-minVal;
       boughtItemIndex=[minIn, itemlist(newitem,newbudget)];
  end

 [minVal minInd]=function findmin(items)
  minVal=0;
  minInd=0;
  for i=1:1:length(items)
   if (items(i)<minVal)
       minVal=items(i);
       minInd=i;
    end
   end

We're learning recursion and how to use it. So we have to use it in the problem. I could do this with a loop easily. I was going to do the cross-out bit, but how would I go about setting that up? That's my main issue here. I can't figure out how to do base cases and how to do it with two inputs and two outputs. — Jessica Marie, Oct 30 '14 at 21:46
I don't understand :/ That doesn't look like recursion to me. You use the function in itself maybe once. I'm just confused. — Jessica Marie, Oct 31 '14 at 00:16
The first part is supposed to go through an item list it looks, so it'd go through my....first input? You renamed some variables, went through the list of items and displayed the indices of items bought, then had the money subtracted. The second bit has some illegal stuff in it. You can't name/label a function like that. I see you're looking to find the minimum of items, then you add the items that are less than the budget into an array. Then you take the budget and subtract the item price. That then gets thrown into a new array. Okay, I can see how that works, sure. — Jessica Marie, Oct 31 '14 at 00:58
The third bit had some more illegal naming in it. You start the minVal and minInd at zero...then populate them with the items and....not sure what minIND =1 is doing. — Jessica Marie, Oct 31 '14 at 00:59

Using Recursion to Generate a List of Items You Can Afford on a Budget

1 Answers1