/prog/ - chocolate

Name: ecrofirT 2009-08-21 9:32

A man has to buy some chocolate boxes
there are different types of boxes:
weight (kg)/// income ($) that the man gets for each box sold
1    10
2    26
3    43
4    52
5    53
6    56
7    71
8    87
9    95
10    100

Due to legal restrictiohns he can only buy 20 boxes and no more than 100Kg total
Also, he wants to choose 2 sizes because it's easier to commercialize.

so I need to write a program in qb/c/java solving this problem

can you help me? just gimme some ideas or pseaudocode please

I think it has something to do with arrays [weight,income] for each type but I'm lost

Name: Anonymous 2009-08-21 9:37

I can haz ur homework? :3

Name: Anonymous 2009-08-21 9:41

it's not homework, I wanna know how it's done because im a nerd

Name: Anonymous 2009-08-21 9:47

SICP
[spoil]I think this can be done cool in Haskell[spoil]HASKAL[/spoil][/spoil]

Name: Anonymous 2009-08-21 9:48

>>3
If that were true, you would have heard about the knapsack problem by now. Even rand(all) did it.

Name: OP 2009-08-21 9:51

yeah I know, but I need it in an imperative language

Name: OP 2009-08-21 9:52

>>3
reading, thanks

Name: Anonymous 2009-08-21 9:55

>>6
Why? You aren't going to learn anything from it, because you can't code.

Name: Anonymous 2009-08-21 10:10

>>1
Forget it, it's NP-hard.

Name: Anonymous 2009-08-21 12:30

>>4
U MENAHASKAL

Name: Anonymous 2009-08-21 15:58

Try regular expressions.

Name: Anonymous 2011-02-03 5:16

Name: Anonymous 2013-05-18 3:06

Quickie Chocolate Treats : http://www.chillinpanda.com/quickie-chocolate-treats

Name: Anonymous 2013-05-18 5:02

http://www.youtube.com/watch?v=M8HhQIs18Q4

Name: Anonymous 2013-05-18 6:49

>>12
hacker!!!!

Name: Anonymous 2013-05-18 7:06

Snapback problem
https://en.wikipedia.org/wiki/Knapsack_problem

Pseudocode is there to, but you will need to do a fair amount of extra work.



// Input:

// Values (stored in array v)

// Weights (stored in array w)

// Number of distinct items (n)

// Knapsack capacity (W)

for w from 0 to W do

  m[0, w] := 0

end for 

for i from 1 to n do

  for j from 0 to W do

    if j >= w[i] then

      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

    else

      m[i, j] := m[i-1, j]

    end if

  end for

end for

If it were C You probably need to create your own function max() i.e.

int max(int a,int b)        {

    if(a>b)

        return a;

    else

        return b;

}

Name: Anonymous 2013-05-18 7:07

>>16
I meant Knapsack problemm too much weed erryday

Name: Anonymous 2013-05-18 7:24

>>16
I hope OP sees this before the deadline for his homework!

Name: Anonymous 2013-05-18 17:49

#!/usr/bin/env python

boxes = [

    (1, 10),

    (2, 26),

    (3, 43),

    (4, 52),

    (5, 53),

    (6, 56),

    (7, 71),

    (8, 87),

    (9, 95),

    (10, 100),

]



best_set = None

best_weight = 0

best_income = 0

for i, box_a in enumerate(boxes):

    for box_b in boxes[:i] + boxes[i+1:]:

        for x in xrange(20):

            box_set = [box_a] * x + [box_b] * (20-x)

            total_weight = sum(w for w, n in box_set)

            total_income = sum(n for w, n in box_set)

            if total_weight <= 100 and total_income > best_income:

                best_set = box_set

                best_weight = total_weight

                best_income = total_income



box_a, box_b = list(set(best_set))

print 'best_set: %s x %d + %s x %d' % (

    box_a, best_set.count(box_a),

    box_b, best_set.count(box_b),

)

print 'total_weight: %dkg' % (best_weight)

print 'total_income: $%d' % (best_income)

Output:
best_set: (4, 52) x 15 + (8, 87) x 5 total_weight: 100kg total_income: $1215

Name: Anonymous 2013-05-19 0:04

>>19
IHNBT

chocolate

1 Name: ecrofirT 2009-08-21 9:32

2 Name: Anonymous 2009-08-21 9:37

3 Name: Anonymous 2009-08-21 9:41

4 Name: Anonymous 2009-08-21 9:47

5 Name: Anonymous 2009-08-21 9:48

6 Name: OP 2009-08-21 9:51

7 Name: OP 2009-08-21 9:52

8 Name: Anonymous 2009-08-21 9:55

9 Name: Anonymous 2009-08-21 10:10

10 Name: Anonymous 2009-08-21 12:30

11 Name: Anonymous 2009-08-21 15:58

12 Name: Anonymous 2011-02-03 5:16

13 Name: Anonymous 2013-05-18 3:06

14 Name: Anonymous 2013-05-18 5:02

15 Name: Anonymous 2013-05-18 6:49

16 Name: Anonymous 2013-05-18 7:06

17 Name: Anonymous 2013-05-18 7:07

18 Name: Anonymous 2013-05-18 7:24

19 Name: Anonymous 2013-05-18 17:49

20 Name: Anonymous 2013-05-19 0:04