这类似于背包或变更生成算法吗？

Question

此处所选项目应为项目1、项目4、项目5和项目6(60+60+80+40=240公斤）

实施例2：-袋最多可容纳180公斤的重量

项目1-60公斤、项目2-30公斤、项目3-55公斤、项目4-30公斤、项目5-70公斤、项目6-48公斤

public List getSelectedItems(List<Presentation> inputList, int knapsackCapacity){
List selectItems;

// optimized algorith  which returns selectItems and inputList containing  the 
//left out items i.e which are not selected;

return selectItems;
}

Answer 1

利用动态规划可以在伪多项式时间(O(nW))内最优求解该问题。您所要做的是对背包0/1的解决方案做一点修改,如下所示：

if w[i] > W
    m[i,W] = m[i-1,W]
else if W - m[i-1, W] < W - m[i-1, W - w[i]] + w[i]
    m[i,W] = m[i-1,W]
else
    m[i-1, W - w[i]] + w[i]

其中w是权重限制，w是元素权重数组。不同的是，您必须最小化w和结果之间的差异，而不是最大化值的总和。

以下是wikipedia的解决方案，并进行了必要的修改：

// Input:
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do
  m[0, j] := 0  // Initialize to 0
end for 
for i from 1 to n do    // for every element in the array
  for j from 0 to W do  // for every possible weight
    if w[i] > j then    // if the element's weight is higher than the max
      m[i, j] := m[i-1, j]  // use the solution that excludes the element
    // else if the diff between the solution that excludes the element and max weight
    // is smaller than the one that uses it, use the former.
    else if (j - m[i-1, j]) < (j - m[i-1, j - w[i]] + w[i])
      m[i, j] := m[i-1, j]
    // else use the element's weight in the solution
    else
      m[i, j] := m[i-1, j - w[i]] + w[i]
    end if

template<typename T>
long Weight(const T& w, int size, const int W)
{
    vector<vector<int>> m(size+1, vector<int>(W+1, 0));

    for(int i = 1; i <= size; ++i)
    {
        for(int j = 0; j <= W; ++j)
        {
            if(w[i-1] > j)
            {
                m[i][j] = m[i-1][j];
            }
            else if((j - m[i-1][j]) < (j - (m[i-1][j - w[i-1]] + w[i-1])))
            {
                m[i][j] = m[i-1][j];
            }
            else
            {
                m[i][j] = m[i-1][j - w[i-1]] + w[i-1];
            }
        }
    }

    return m[size][W];
}