寻找子集组合以实现给定总和同时保持成本最低的算法

Question

我有一个问题，我有一个具有以下结构的元素数组:

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

现在，我需要选择一个或多个元素的组合，其中每个元素都有一个唯一的索引，即没有一个元素可以有相同的索引。这种元素组合的长度之和应该恰好等于 N，如果有多种这样的组合，那么我需要选择成本最低的一种。

有什么想法吗？我目前的解决方案不起作用，所以我不确定是否应该在这里分享它。谢谢!

编辑:这是我现在拥有的。 selected 是所选元素的索引集，startI 是起始索引，ranageMax 是结束索引(全局)。 L 是所需长度，M 是我们拥有的最大金额，因此成本必须小于它。

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

在关于 knapsack problem 的维基百科文章中，有一个动态规划算法的描述，该算法组合权重以最大化利润。要解决原始问题中描述的问题，必须组合长度 以优化成本。我们使用二维状态空间如下。

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

基于该定义，我们得到以下递归关系。

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

这个递归关系是正确的，因为最小值中的第一项对应于选择索引为 i 的项目进入解决方案，而第二项对应于选择索引为 i 的项目 不 进入解决方案。状态空间必须用正无穷大的值初始化，除了对应于单个项目的选择的状态。然后可以通过在外循环中增加 i 并迭代

中的所有可能值，以自下而上的方式评估状态

{0,....,N}

在内循环中。经过评估，可以在 C[n,N] 中找到最小成本。如果需要所需的项目选择，则必须使用回溯或辅助数据结构来生成它。

请注意，在上面的演示中，如果任何参数为正无穷大，我们假设值的相加为正无穷大。