• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Question about a dynamic programming problem

 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,


I came across the following question on careercup.com:


There are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get at least one dish of his choice. What is the minimum number of different type of dishes we can order?

Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row.

n = 6 k = 7
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 1 0 0
0 0 1 0 0 1 0
0 0 0 1 0 0 1

Output
3

Explanation
Take dish number 5,6,7.



I was able to see that greedy approach would give me an incorrect answer of 4 (select dishes that are favorites of maximum number of people). However, I feel that dynamic programming approach would be apt in this case. So, I'm thinking in order to solve the main problem, it can be thought of as making a choice of whether to select a particular dish or not.

I think the following recursion can be used to determine the solution

opt(d,people_to_feed)=Min(1+opt(d-1, people_to_feed - people_fed) + opt(d-1,people_to_feed))

where d is a dish number

I wrote the following code



The result comes back as 0 instead of 3.

Please let me know if there are some modification with which this approach can produce the correct result.

Thanks
Varun
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Varun Gokulnath wrote:
I think the following recursion can be used to determine the solution

opt(d,people_to_feed)=Min(1+opt(d-1, people_to_feed - people_fed) + opt(d-1,people_to_feed))

where d is a dish number



Can you elaborate your algorithm a bit? I'm not sure what you are trying to do here.

Henry
 
Gvarun Rao
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

people_fed should've been people_fed_by_d.

I was thinking that if dish d is selected then : [number of people to feed - number of people fed by dish d] will be remaining. The other option is to not pick dish d. Then, we still have : [number of people to feed] remaining.
Then I continued the recursion with dish d-1.

opt(d,people_to_feed)=Min(1+opt(d-1, people_to_feed - people_fed_by_d) + opt(d-1,people_to_feed))
 
Marshal
Posts: 79177
377
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You are trying to write code before you have got your algorithm sorted out. What you are trying to do is find the smallest subset of dishes such that
∀ x • ∃ y • likes(xy)
… where x ∈ diners, y ∈ dishes and likes(xy) should have an obvious meaning.
 
Ranch Hand
Posts: 62
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Varun,

Your algorithm is wrong. It does not take into account that if for dish X you feed n people, none of those precisely n people must be taken into account when counting the people fed by dish X-1.
 
Gvarun Rao
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for all the replies. I was able to fix my code based on the feedback I received:



This code prints:

3
Dishes chosen [5, 6, 7]
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Varun,

your code does indeed print 3 and [5, 6, 7], but when I supply only the first
three rows in stead of all 6, the output is again 3 and [5, 6, 7]. And
ditto when I supply only the first row. It seems that your recursion is
not yet fully correct.

I've been giving this problem a thought or two as well. My main concern
was this: when you start with row one, i.e. one person and seven dishes,
and you add the next two persons, you are bound to believe that dish 1
would be a perfect answer, and rightly so.

But in the end, after having added the sixth person, we have made the
swtich from dish 1 to dishes 5, 6, and 7. So, somewhere in the process
of adding people, there must be this switching moment. Now, going from
only one dish to three seems quite a huge step to make for a simple
recursion. The impression I got was that adding another person or
dish would involve checking all new possibilities, but then we
would end with a brute force method in disguise. And that would lead
to the dreaded O(2^n).

I did not Google for any theoretical solution, that would spoil the nice puzzle.
Let us know when you have fixed your recursion.

Greetz,
Piet
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic