# QuestionHow would you solve this problem?

#### sdannygu

##### Member
Hello, i am just starting learning C# and i got this problem to solve.

Given:
TargetWeight
Two different Weights (as many as you wish)

Question:
Using either one of the weights or both, what is the closest weight you can get to the target weight?

Requested output:
The closest weight and a number of each weight was used.

For example: for given TargetWeight of 230 grams and two weights of 170 grams and 40 grams. Which combination of these weights will give the closest to 230 grams?

I am struggling already for two days. Any help will be appreciated.

Thanx.

Thanx, but i don't see the relation.
According to Coin Problem ( as long as the set of coin denominations has no common divisor greater than 1):
Coin 1 - 17, Coin 2 - 4. The largest integral number which cannot be made by these "coins" is 47.
My problem:
Weight 1 - 17, Weight 2 - 4. Target Weight 22. What is the closet weight i can get with x number of weights 17 and y number of weights 4 to 22? Logically i would say 21, but i need to write a code for any numbers.

It does but, ones you put a limitation to the problem in terms of below the TargetWeight and minimum number of weights the solution becomes easy. My problem has no conditions. I actually understand the algorithm. My problem is to spill it into C#.

Your problem is simply the unbounded knapsack problem. Which algorithm are you talking about?

The UKP has no limitations on number of items, but still has a limitation of below the given weight.

Yes. And isn't the same true for your problem? You have two classes of items of specific weights. You need to figure how many of each item will add up a close to or equal to the target weight.

I do, but in my case the closest weight can be more than the given.

So you are saying given weights 3 and 5 and the target weight of 4, the correct answers can be either 3 or 5; and the target weight of 14 the correct answer can be either 5*2+3 or 5*3? So for 17 what is the correct answer?

Correct. For 17 it will be 17. Four times 3 and 5.

In your shoes, the way I would tackle this problem is first find a UKP solution for less than or equal to the target weight. Call this solution1. If solution1 equal to the target, then you are done. Otherwise, solve for the UKP's of target + 1 to 2 * target - solution1 - 1. When you get a solution that is less than abs(target - solution1) then you have your answer. If you can't find a solution less than abs(target - solution1), then solution1 is (one of) the best answer(s) you can get.

Last edited:

Replies
8
Views
531
Replies
0
Views
529
Replies
1
Views
939
Replies
1
Views
793
Replies
4
Views
704