Knapsack Problem Without Value

geez...@gmail.com

unread,

Dec 12, 2013, 9:08:56 PM12/12/13

to

Hi,

I wanna ask about Knapsack. I do understand what Knapsack is about. But this one i faced is a different problem. There is no value. I mean, it's like this, for example.

I have 4 beams [X0, X1, X2, X3]. Each 1, 2, 2, 3 cm long. I want to make a new 6 cm long connected-beam from these 4 beams. I can make it from some of these. The output will print:

1, 2, 3 #(X0, X1, X3)

You understand what my problem is? Can you help me?

Sincerely,

Gary Herron

unread,

Dec 12, 2013, 9:49:14 PM12/12/13

to pytho...@python.org

No, I don't understand what your problem is.

You say there are no values but then you give 4 values (1, 2, 2, and 3), and then you *solve* the Knapsack problem like this:

1, 2, 3 #(X0, X1, X3)

That looks like a fine solution to me.

Questions:

Exactly *what* is the problem. If you tell us *carefully* what the problem is, we may try to solve it.
This is a Python list. Does your problem have anything to do with Python?
Is this a homework problem? We generally don't solve homework problems here (since you don't learn anything that way), but we are certainly happy to help you learn.

Gary Herron

-- 
Dr. Gary Herron
Department of Computer Science
DigiPen Institute of Technology
(425) 895-4418

geez...@gmail.com

unread,

Dec 13, 2013, 4:38:47 AM12/13/13

to

No, this isnt homework. There is a website called Jollybee (Its available only in Bahasa) Here is the link if you dont believe me http://jollybee.binus.ac.id/oj/site/problemset/problem/code/HS10F/

Im just got bored and trying to have fun.

Not values like that, i mean, everywhere, I found the pseudocode only teach me with 2 variable. Mostly weight and its values ($). For short, this problem I faced is only the weight, no values($).

Hope you get it.

Mark Lawrence

unread,

Dec 13, 2013, 5:04:57 AM12/13/13

to pytho...@python.org

Would you please read and action this
https://wiki.python.org/moin/GoogleGroupsPython to prevent us seeing the
double line spacing above, thanks.

--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

Ian Kelly

unread,

Dec 13, 2013, 6:16:29 AM12/13/13

to Python

With no values, where the goal is just to make a specific sum, it's
the subset sum problem, not the knapsack problem.

Steven D'Aprano

unread,

Dec 14, 2013, 4:28:33 AM12/14/13

to

On Fri, 13 Dec 2013 01:38:47 -0800, geezle86 wrote:

> On Friday, December 13, 2013 9:08:56 AM UTC+7, geez...@gmail.com wrote:
>> Hi,
>>
>> I wanna ask about Knapsack. I do understand what Knapsack is about. But
>> this one i faced is a different problem. There is no value. I mean,
>> it's like this, for example.
>>
>> I have 4 beams [X0, X1, X2, X3]. Each 1, 2, 2, 3 cm long. I want to
>> make a new 6 cm long connected-beam from these 4 beams. I can make it
>> from some of these. The output will print:
>>
>> 1, 2, 3 #(X0, X1, X3)
>>
>> You understand what my problem is? Can you help me?
>

> No, this isnt homework. There is a website called Jollybee (Its
> available only in Bahasa) Here is the link if you dont believe me
> http://jollybee.binus.ac.id/oj/site/problemset/problem/code/HS10F/
>
> Im just got bored and trying to have fun.
>
> Not values like that, i mean, everywhere, I found the pseudocode only
> teach me with 2 variable. Mostly weight and its values ($). For short,
> this problem I faced is only the weight, no values($).

With only one value, I think it counts as a variation of the Change-
Making Problem:

http://en.wikipedia.org/wiki/Change-making_problem

--
Steven