Algorithm for finding subset combination for achieving a given sum, while keeping the cost minimum

Question

I have a question where I have an array of elements with the following structure:

struct Band
{
    int index;
    int length;
    int cost;
};

Now, I need to select a single or a combination of elements, where each of the elements having a unique index, i.e, none of the elements can have the same index. This combination of elements should have a sum of their lengths exactly equal to N, and if there are multiple such combinations, then I need to select the one with the minimum cost.

Any ideas? The current solution I have is not working, so I'm not sure if I should share it here or not. Thanks!

EDIT: Here's what I have right now. selected is the set of indices of elements selected, startI is starting index, ranageMax is the ending index (global). L is the required length and M is the maximum money that we have, so the cost must be lesser than it.

void knapsack(struct Band rubber[], int currLen, int cost, int startI, set<int> selected)
{
    if(startI == rangeMax)
    {
        /*&root[startI].length = currLen;
        root[startI].cost = cost;*/
        cout << "\n";
        return;
    }
    if(cost > M || currLen > L)
    {
        cout<< "\n";
        return;
    }
    if(currLen == L)
    {
        //cout << "Candidate : " << cost << endl;
        cout << "\n";
        if(cost < minv)
            minv = cost;
        return;
    }
    for(int i=startI; i<rangeMax; ++i)
    {
        //knapsack(rubber, currLen, cost, startI+1, selected);
        if(selected.find(rubber[i].index) == selected.end())
        {
            selected.insert(rubber[i].index);
            cout << rubber[i].length << " ";
            int tempCurrLen = currLen + rubber[i].length;
            int tempCost = cost + rubber[i].cost;
            /*root[i].length = currLen;
            root[i].cost = cost;*/
            knapsack(rubber, tempCurrLen, tempCost, i+1, selected);
            selected.erase(rubber[i].index);
        }
    }
}

Added my "solution" to the question, please don't judge me :P — shantam777
– shantam777, Commented Oct 21, 2016 at 16:06

Codor · Accepted Answer · 2016-10-21 16:17:43Z

2

In the wikipedia article about the knapsack problem, there is a description of a dynamic programming algorithm which combinatorializes the weight in order to maximize the profit. To solve the problem described in the original question, one has to combinatorialize the length in order to optimize the cost. We use a two-dimensional state space as follows.

C[i,j] is defined as the minimum cost attainable for a selection of items
       with indices in {1,...,i} of total length exactly j
       or positive infinity if there is no such selection

Based on that definition, we obtain the following recurrence relation.

C[i,j] = min{ C[i-1,j-weight[i]] + cost[i], C[i-1,j] }

This recurrence relation is correct by reasoning that the first term in the minimum corresponds to choosing the item with index i into the solution while the second term corresponds to chosing the item with index i not into the solution. The state space has to be initialized with a value of positive infinity, except for the states which correspond to the choice of a single item. The states can then be evaluated in a bottom-up way by increasing i an an outer loop and iterating over all possible values in

{0,....,N}

in an inner loop. After evaluation, the minimum cost can be found in C[n,N]. If the desired selection of items is desired, one would have to use either backtracking or auxiliary data structures to generate it.

Note that in the presentation above, we suppose that addition of values is positive infinity if any of the arguments is positive infinity.

answered Oct 21, 2016 at 16:17

Codor

17.6k9 gold badges32 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

shantam777 Over a year ago

Thanks for the answer! However, this doesn't take into account the grouping problem, i.e., there can only be one element for a particular index. Also, just a small suggestion, in the recurrence relation it should be

shantam777 Over a year ago

oops, accidentally pressed enter. So I think the recurrence relation should be : codeC[i,j] = min{ C[i-1,j-length[i]] + cost[i], C[i-1,j] } code And the minimum cost would be found in C[L,N]. Do correct me if I'm wrong!

Collectives™ on Stack Overflow

Algorithm for finding subset combination for achieving a given sum, while keeping the cost minimum

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related