[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 700
  • Last Modified:

Knapsack Problem

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
ssharp77
Asked:
ssharp77
  • 3
  • 2
3 Solutions
 
blissbearCommented:
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
 
blissbearCommented:
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
 
blissbearCommented:
Otherwise, here are your fomulae: http://en.wikipedia.org/wiki/Knapsack_problem :)
0
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 
GwynforWebCommented:
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
 
ssharp77Author Commented:
Thank you.
0
 
GwynforWebCommented:
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

Receive 1:1 tech help

Solve your biggest tech problems alongside global tech experts with 1:1 help.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now