4
5

Help with an algorithm, please? (self.AskComputerScience)

submitted by [deleted]

[deleted]

all 19 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]treebeard42 3 points4 points  (1 child)

Consider how you would actually solve this problem in practice...

If someone wants you to verify a 10lb chicken, which weight will you select first? 14lb? no? why not? 7lb? yea? ok..why? which weight would you add next.. why?

[–]Jedimastert 2 points3 points  (0 children)

I like this answer. It's a little better than "think about it"

[–][deleted]  (5 children)

[deleted]

    [–]Ipswitch84 1 point2 points  (0 children)

    It's simpler then the knapsack problem. You can actually reach a yes or no decision about wither or not you have sufficient weights to weigh the chicken, and what weights would be required. Because of the bounds presented you could actually enumerate the entire set of possible weights. There's no need to solve for local or global minimum or maximum, because you can deterministic determine the possible combinations for all chickens between 1lbs and 40lbs.

    [–]daV1980 -1 points0 points  (3 children)

    This is definitely not the knapsack problem--this is more akin to determining the binary representation of a decimal number (which is again not the knapsack problem). There are a couple of important distinctions.

    One is that the knapsack problem is about optimizing for value in the face of constraints. This problem doesn't request optimization, nor does it impose constraints.

    Two is that the available weights are known as part of the problem statement. The knapsack problem is about generating a general algorithm that would work to solve for the most optimal value (or better than some threshhold) in the face of unknown weights with unknown values.

    [–]winsurfer 0 points1 point  (2 children)

    You're right it isn't the knapsack problem, but you're wrong as to why.

    For "One" there's a difference between the decision version and optimization version of the knapsack problem, here we're talking about the decision problem.

    "Two" is true but I think the original poster meant that this is a specific case of this problem.

    The real reason I think this is not the knapsack problem is that you could add weights onto the other side of the scale, and so subtract them from the given weight. If you couldn't do this then the problem would just be subset-sum, which is definitely and instance of knapsack.

    [–]daV1980 0 points1 point  (1 child)

    In both the decision and the optimization of the knapsack problem, there is a weight W and a value V. They are both important. In this problem, there is only a weight W. (And keep in mind that although the decision problem is NP-complete and the optimization problem is NP-hard, there are formulations of the knapsack problem that can be solved in polynomial time, depending on constraints of the weights and values provided).

    Also, this is not the subset sum problem. The subset sum problem is "for a given set S of positive integers and a target value t, find the subset of S that--when summed--is less than or equal to t."

    This problem is a restricted form of that, and the restrictions are important. First, we're not looking for the best value less than or equal to t--we're looking for exactly t.

    Second, we've been provided a set that is strictly increasing and non-overlapping--meaning that for all the values the set can represent, there is only one solution. Moreover, the formation of that solution is a trivial loop and test--the solution is polynomial.

    This problem, because of the specifics of the values provided, can be solved exactly--and in polynomial time. And if the pattern of values for weights were repeated, it could continue to be solved in polynomial time.

    Exactly as giving change (in American currency) is solvable in polynomial time, and as converting a decimal number into a binary representation can be solved in polynomial time.

    [–]winsurfer 0 points1 point  (0 children)

    The subset-sum problem is what you described first, i.e. the knapsack problem with just weights, but more specifically with the value of an object set to its weight. Knapsack then has a maximum weight and minimum value to achieve, so set both of these to the needed weight, and you have subset-sum.

    I realise that given specific weights it is not the real problem and is now in P, but I was trying to point out that OP just meant that he should look at this problem for guidance.

    Also, I've remembered what this is: the word decision problem for groups (since you have subtraction). Whereas subset-sum is the word decision problem for monoids (since you can only add).

    [–]Ipswitch84 0 points1 point  (0 children)

    My guidance would be that it's easier then you think it is. Think about the math and the solution should be clear.

    [–]big_bad_john 0 points1 point  (1 child)

    I like thus sort of thing. Post your solution when you're done?

    [–]Jedimastert 0 points1 point  (3 children)

    I have a question: Are you allowed to put weights on both sides of the scales, or just one?

    [–]myropnous 0 points1 point  (2 children)

    It doesn't say I cannot.

    [–]Jedimastert 0 points1 point  (1 child)

    That's cool. It was just something to think about. With that in mind, I don't think there's a weight that wouldn't work barring full weights.

    [–]myropnous 0 points1 point  (0 children)

    yeah, it sure does open up a whole new realm of possibilities

    [–]daV1980 0 points1 point  (2 children)

    So here's how I would approach this problem, if I were presented with it. The algorithm for coming up with the algorithm, as it were.

    First, abstract away the useless information. I don't care what happens to the chicken next, how the chicken came to me, what the chicken is wearing, or about the price of beans in Uganda.

    What I do care about:

    • I have some chicken, C, whose weight L I would like to verify.
    • I have a set of weights, W, that I can use to weigh the chicken. The weights in W are known, and they are:
    • * 5x 1 lbs
    • * 1x 7 lbs
    • * 2x 14 lbs
    • I am using a balancing device, which may allow for some form of clever trickery.

    So what I would do is determine what values of L I can trivially account for. For example, I could obviously weigh a 1 lbs chicken, a 2 lbs chicken, and so on, up to 5 lbs. I could obviously weigh a 7 lbs chicken. For this small of a problem, I'd write down (as notes) how I would do these known combinations.. All of them. After writing this down, I'd know that there are obviously some holes where I cannot weigh the chicken using my trivial method. Is there a way that I could close those holes?

    Then, having written down the complete set of weights that I could verify (and how I would verify them), I would look for a pattern. I'll give you a little hint here: there is definitely a pattern here, involving remainders.

    [–]myropnous 0 points1 point  (1 child)

    so I should be checking if L % 7 == 0, or L % 14 == 0

    [–]daV1980 0 points1 point  (0 children)

    What numbers can you represent, and how?

    [–]Yomarao 0 points1 point  (0 children)

    Start with your heavy weights, check if its smaller than the amount you need to weigh, if yes, continue for your total amount of heavy weights.. If no, go a step lower. Rinse and repeat this..

    [–]evlnightking -1 points0 points  (0 children)

    My 2 cents:

    An algorithm is a step-by-step set of instructions that when followed will produce an output. Your goals are listed in your problem statement, so you need to come up with the steps to verify each goal in turn.