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);
        }
    }
}

Answer 1

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.