Hello Friends, In the previous article I have discussed about the knapsack algorithm with step by step guide. In the article I discussed how we can create a cache of the sub solution to solve a bigger solution. But as we all know only understanding a solution would not be helpful. Finally we need some implementation of the learning we had in the last article. In this article I will work on a real Knapsack practical problem with code example.
Knapsack practical problem CONFERENCE TRACK MANAGEMENT
You are planning a big programming conference and have received many
proposals which have passed the initial screen process but you are having
trouble fitting them into the time constraints of the day — there are so many possibilities! So you write a program to do it for you.
* The conference has multiple tracks each of which has a morning
and afternoon session.
* Each session contains multiple talks.
* Morning sessions begin at 9am and must finish by 12 noon, for lunch.
* Afternoon sessions begin at 1pm and must finish in time for the networking
event.
* The networking event can start no earlier than 4:00 and no later than 5:00.
* No talk title has numbers in it.
* All talk lengths are either in minutes (not hours) or lightning (5 minutes).
* Presenters will be very punctual; there needs to be no gap between
sessions.
Note that depending on how you choose to complete this problem, your
solution may give a different ordering or combination of talks into tracks. This is acceptable; you don’t need to exactly duplicate the sample output given here.
Test input:
Writing Fast Tests Against Enterprise Rails 60min
Overdoing it in Python 45min
Lua for the Masses 30min
Ruby Errors from Mismatched Gem Versions 45min
Common Ruby Errors 45min
Rails for Python Developers lightning
Communicating Over Distance 60min
Accounting-Driven Development 45min
Woah 30min
Sit Down and Write 30min
Pair Programming vs Noise 45min
Rails Magic 60min
Ruby on Rails: Why We Should Move On 60min
Clojure Ate Scala (on my project) 45min
Programming in the Boondocks of Seattle 30min
Ruby vs. Clojure for Back-End Development 30min
Ruby on Rails Legacy App Maintenance 60min
A World Without HackerNews 30min
User Interface CSS in Rails Apps 30min
Test output:
Track 1:
09:00AM Writing Fast Tests Against Enterprise Rails 60min
10:00AM Overdoing it in Python 45min
10:45AM Lua for the Masses 30min
11:15AM Ruby Errors from Mismatched Gem Versions 45min
12:00PM Lunch
01:00PM Ruby on Rails: Why We Should Move On 60min
02:00PM Common Ruby Errors 45min
02:45PM Pair Programming vs Noise 45min
03:30PM Programming in the Boondocks of Seattle 30min
04:00PM Ruby vs. Clojure for Back-End Development 30min
04:30PM User Interface CSS in Rails Apps 30min
05:00PM Networking Event
Track 2:
09:00AM Communicating Over Distance 60min
10:00AM Rails Magic 60min
11:00AM Woah 30min
11:30AM Sit Down and Write 30min
12:00PM Lunch
01:00PM Accounting-Driven Development 45min
01:45PM Clojure Ate Scala (on my project) 45min
02:30PM A World Without HackerNews 30min
03:00PM Ruby on Rails Legacy App Maintenance 60min
04:00PM Rails for Python Developers lightning
05:00PM Networking Event
Approach For Solving the Problem at hand
We can use the brute force algorithm to solve this particular problem. But looking at the possible outcomes and the number of options it can take us huge amount of time to design the solution. And the solution would not be an optimized one.
Now can we try to relate it to the Knapsack problem we tried to solve in the previous post. Here we have some time limit for each day. We can think of the day as equivalent to knapsack. Where we have some time(specifically minutes) to hold some particular number of events. We can imagine events with minutes as the items with some weights.
The only thing missing here in this problem is the value of each item. As we only need to find if a particular event can be included or not.
Code Solution for the knapsack Problem
The below code is the part of the solution. It is basically the engine where which will take the input parameters as capacity and the items which we want to arrange in that capacity.
Can you get the solution for the above problem once you are provided by the core engine C# code provided below.
public class GenericEngine: IEngine where T : IItem { /// /// This engine will return the best solution by creating the sub solutions which is based on the knapsack algorithum. The items returned will have the total /// capacity equal to the capacity passed to the solution. The solution will keep creating cache which will ne used for further processing and making the algo /// faster. /// ////// The capacity to be passed to the algo based on which we are getting the best matching items /// The items from which we need to get the best suited items based on the capacity. /// public List GetTheBestSuitableItem(int capacity, IList items) { try { // Create arrays for keeping track of the maximum value for each sub-solution // and which items to include, respectively: var maxValues = (int[,])Array.CreateInstance(typeof(int), items.Count + 1, capacity + 1); var doInclude = (bool[,])Array.CreateInstance(typeof(bool), items.Count + 1, capacity + 1); // Notice, that at this point, both arrays are initialized with 0's and false, respectively. // Fill out the cache-arrays, starting with the smallest sub-solution first... for (var i = 0; i < items.Count; i++) { var currentItem = items[i]; var row = i + 1; for (var c = 1; c <= capacity; c++) { // What is the maximum possible value for the two cases where the // item is included and excluded from the final solution, respectively? var valueExcluded = maxValues[row - 1, c]; var valueIncluded = 0; if (currentItem.Value <= c) valueIncluded = currentItem.Value + maxValues[row - 1, c - currentItem.Value]; // Only use the current item if it results in a higher value: if (valueIncluded > valueExcluded) { maxValues[row, c] = valueIncluded; doInclude[row, c] = true; } else { maxValues[row, c] = valueExcluded; } } } // Find out which items that actually constitutes the above found solution value... var chosenItems = new List (); // Iterate backwards, starting from the last item... for (var row = items.Count; row > 0; row--) { // If the current item should not be included, just skip it and look at the next one: if (!doInclude[row, capacity]) continue; // Otherwise, add it to the list of chosen items: var item = items[row - 1]; chosenItems.Add(item); // Now, with that item chosen, the next sub-problem's capacity is correspondingly smaller: capacity -= item.Value; } return chosenItems; } catch (Exception ex) { throw ex; } } }
Leave a Reply