• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • paul wheaton
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Tim Holloway
  • Carey Brown
  • salvin francis

Difficult University Assignment - Where to start ?

 
Ranch Hand
Posts: 39
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Apologies if this is in the wrong forum.

I would class myself as efficient at Java but awful at problem solving without a bit of help.

I just cant get the knack of breaking a problem into smaller steps and solving each step individually while testing in parallel.



(Just in case the image is difficult to read ... Link to larger picture )


I have a blank A4 page in front of me and no idea how to go about tackling this problem.

Any help on how to get started would be appreciated.
 
Saloon Keeper
Posts: 3443
149
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Kevin,

well, first things that come up to me are:

1) turn the different room Types into classes
2) make a List of the type of room that is cheapest when that room contains 1, 2, 3 or 4 persons.
3) ever heard of dynamic programming? You can apply that here. I won't give details here, but have a look at this topic: Dynamic Programming
Suppose that you have a grid with horizontally the number of persons 1, 2, 3, 4, 5, 6, 7, and vertically the Room Types?
 
Piet Souris
Saloon Keeper
Posts: 3443
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A hint, after my perhaps somewhat cryptic reply:

suppose you have the cheapest solution for a group of 1 person, 2 persons, 3 and 4.
Now, let the arrar a[] be such that a[k] contains the cheapest solution for a group of K persons.
It is clear what a[0] is. And also what a[1] is, given that you already have the cheapest solution for a group of 1.
Suppose person 2 enters the scene. Now, mr 2 can be given the cheapest solution for 1 person as well, total cost being 2 * a[1], but we can also put the two into th cheapest solution for a group of 2 persons.
What will a[2] be? And then mr 3 comes in. We can give him a[1] as well, now having a total cost of a[2] + a[1]. But there is another solution as well. What is that? And how do we continue?

 
Kevin Mckeon
Ranch Hand
Posts: 39
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've been doing a good bit of research into the topic of Dynamic Programming since your reply.

I want to get a good grasp of DP before tackling this problem.

I have a good understanding now of the Longest Increasing SubSequence Problem found here Link to Increasing SubSequence Problem

I have one question, does your method and hint above use the method of Memoization or Tabulation when finding the optimal solution. Is it possible to use both methods and still get a solution ?

Memoization vs Tabulation

 
Piet Souris
Saloon Keeper
Posts: 3443
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Kevin,

Kevin Mckeon wrote:I have one question, does your method and hint above use the method of Memoization or Tabulation when finding the optimal solution. Is it possible to use both methods and still get a solution ?

Memoization vs Tabulation


Well I didn't know these terms when it comes to DP, but your link is very clear about that (GeeksForGeeks is an excellent site for all kinds of algorithms, I've used it often myself).

I always use the Bottom Up approach, but it is certainly possible to do the Top Down way. I don't think it is more difficult, but as said I have never used it that way. Maybe if you have come up with a solution, that we discuss how to do it the other way?

One possible problem with the top down is that a recursion may lead to a StackOverflow, which happened to me lately. I was given an N-nary Tree (a Tree where each Node can have 0 to N nodes). Each Node had a value that was the sum of its autonomous value and the sum of all its Nodes underneath. Now, I had this implemented recursively, so all I needed was: topnode.getValue(), but of course that Tree I was given contained 100.000 Nodes, completely sequentiial. So I had to think of something else.
 
Can't .... do .... plaid .... So I did this tiny ad instead:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!