java - 这类似于背包或找零算法吗？

Question

this problem involves trying to fit items of different weights into a bag so that the bag ends up with a specified total weight or closest to total specified weight.

示例 1:-包最多可承重 240 公斤

Item1- 60kg, Item2- 30kg, Item3- 55kg, Item4- 60kg, Item5- 80kg, Item6- 40kg, Item7- 7kg,

这里选择的元素应该是Item1, Item4, Item5 and Item6(60+60+80+40 = 240 kg)

示例 2:-包最多可承重 180 公斤

Item1- 60kg, Item2- 30kg, Item3- 55kg, Item4- 30kg, Item5- 70kg, Item6- 48kg

这里选择的元素应该是Item1, Item4, Item5 and Item6(60+70+48 = 178 kg)

最接近180公斤

这是我的模板方法

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

网上有些人称之为Knapsack problem的最简单形式因为它没有任何与之相关的好处/利润，所以有人称之为 Change-making problem

无论它属于什么类别，我都无法获得它的算法，因此无法从中制作 Java 程序。这里有什么帮助吗？

Answer 1

这个问题可以使用动态规划在伪多项式时间 ( O(nW) ) 内得到最佳解决。您需要做的是像这样修改 Knapsack 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

二维数组 m , 是内存表，在算法的最后，m[k, p]拥有从 0 到 k 的元素的最佳解决方案最大重量p .

编辑:我在 C++ 中实现并测试了它，它应该很容易移植到 Java:

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