?
Solved

Knapsack Problem

Posted on 2009-04-04
6
Medium Priority
?
683 Views
Last Modified: 2012-06-27
I am uncertain how to solve the following problem and would like some guidance in doing so. Any help is greatly appreciated. Thank you in advance!

Find a subset of the 12 experiments with a total weight of 700 kilograms and a total rating of 49.

Below is a list of the rating and weights, respectively:

9 / 264
8 / 65
8 / 104
8 / 203
7 / 80
6 / 7
6 / 170
6 / 188
5 / 36
4 / 22
3 / 25
2 / 92
0
Comment
Question by:ssharp77
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
6 Comments
 
LVL 4

Accepted Solution

by:
blissbear earned 1350 total points
ID: 24070100
Well, I would start by realizing the exclusion subset is smaller in total. If you add up all the weights, you will find they total 72, which means you need to exclude items which would total 23 kg.  The total rating for the entire set is 1256, so you need to exclude 556.

Can you determine a subset that meets these totals?
0
 
LVL 4

Assisted Solution

by:blissbear
blissbear earned 1350 total points
ID: 24070106
Also, the total weight is 700 kg, so you can start finding subsets that total to a factor of 10, since those subsets have to add up to be divisible by 10.
0
 
LVL 4

Expert Comment

by:blissbear
ID: 24070109
Otherwise, here are your fomulae: http://en.wikipedia.org/wiki/Knapsack_problem :)
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 31

Assisted Solution

by:GwynforWeb
GwynforWeb earned 150 total points
ID: 24071899
This is not a knapsack problem, although it is similar. The knapsack problem would read,

"Find a subset of the 12 experiments with a total weight of not exceeding 700 kilograms that maximizes the total rating."

I am guessing that a dynamic programming approach could be used for this as well.
0
 

Author Closing Comment

by:ssharp77
ID: 31566695
Thank you.
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 24073096
I would have been interested to know if this problem is to be solved as exactly stated or is in fact just a knapsack problem.   As stated the problem can also be formulated as a dynamic programming problem.
(note: the link refers to the knapsack not this problem although it is a guide to the solution formulation)
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question