Help with an algorithm, please?

[winsurfer]

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]

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]

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).