CODEWITHSUNDEEP
c#algorithmsumexpression
eaydemir
eaydemir

Reputation: 47

The sum of the closest record to the desired value

How do I write that method has the following results, how can i create Filter metod? The sum of the closest record to the desired value

class Program
{
public Program()
{
    List<item> items = new List<item>() 
    {
        new item () { Id = 11 , Value = 100},
        new item () { Id = 12 , Value = 300},
        new item () { Id = 13 , Value = 10},
        new item () { Id = 14 , Value = 20},
        new item () { Id = 15 , Value = 200},
        new item () { Id = 16 , Value = 600},
        new item () { Id = 17 , Value = 7},
        new item () { Id = 18 , Value = 3},
        new item () { Id = 19 , Value = 3},
        new item () { Id = 20 , Value = 2},
        new item () { Id = 21 , Value = 70},
        new item () { Id = 22 , Value = 200},
        new item () { Id = 23 , Value = 300},
        new item () { Id = 24 , Value = 250},
        new item () { Id = 25 , Value = 900},
        new item () { Id = 26 , Value = 700},
        new item () { Id = 27 , Value = 400},
    };

    var list_1 = items.Filter(1000);    //expect id : 11,12,16
    var list_2 = items.Filter(25);      //expect id : 13,17,18,19,20
    var list_3 = items.Filter(400);     //expect id : 11,12
    var list_4 = items.Filter(1935);    //expect id : 11,12,13,14,15,16,18,20,25
    var list_5 = items.Filter(101);     //expect id : 11
    var list_6 = items.Filter(150);     //expect id : 11,13,14,17,18,19,20

}

Upvotes: 1

Views: 88

Answers (2)

John Askew
John Askew

Reputation: 233

You need to approach this in steps

  1. Sort the list by value descending
  2. Iterate over the list until you get to the first value equal to or less than the filter value
  3. Create a list of the remaining items and group them together until the sum of grouped items equals or exceeds the filter value
  4. Finally, check if the sum exceeds the filter value and if so remove the item with the smallest value
  5. Continue the iteration until the list is empty or until you have an exact match

Note: This is a simplistic implementation in the sense that it will get a close match instead of an exact match as follows:

values: 3,5,7,9,11

filter value: 19

returns 11, 7 (total : 18)

A better algorithm would return 11, 5, 3 (total: 19) but this would be more computationally expensive requiring multiple iterations of the values.

How important is accuracy in your scenario?

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726639

This is a variation of 0/1 Knapsack Problem, which has a solution that is pseudo-polynomial in both space, which is O(k), and time, which is O(Tk), where k is the number of items, and T is the expected number.

The article linked above has simple pseudocode for solving the problem. You should modify it to use a pair of single-dimension arrays instead of a 2D array to conserve memory. This is possible, because each iteration references at most two rows in a 2D array - the one being constructed, and the one immediately in front of it.

The algorithm constructs an array of reachable totals. You can run the algorithm in reverse to extract the sequence of IDs that lead to the particular result for which you are filtering.

Upvotes: 2

Related Questions