1

这个问题有一个简单的dp解决方案：

#include <vector>
#include <limits>

int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
    size_t n = wts.size();
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n+1, 0));
    for (size_t j = 1; j <= n; j++) {
        for (int w = 1; w <= W; w++) {
           if (wts[j-1] <= w) {
               dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
           }
           else {
                dp[w][j] = dp[w][j - 1];
           }
        }
    }
    return dp[W][n];
}

但是我怎么知道拿走了什么东西呢？

4

3 回答 3

0

您的方法的主要问题是缺乏将项目的概念编码为实体。您应该创建一个类型“项目”（使用classorstruct关键字）来描述具有重量、成本和某种标识符（名称或编号）作为成员的项目。这样，您只需要发送一个项目向量，任何解决方案都将是这些项目的列表，它可以回答您的问题。

编辑

根据要求，这里有一个更实际的解释，说明如何天真地让它工作。

创建一个类型，item其中包含单个项目的所有信息。取一个std::vector<item>作为输入来替换两者wts和cost然后，最小的可能更改是更改dp，以便它存储由运行成本和项目列表组成的对。这会给它 type std::vector<std::vector<std::pair<int,std::vector<item>>>>。也就是说，对于每个存储的（部分）解决方案，跟踪其成本和提供此解决方案的项目。

这种 fordp看起来相当可怕，但如果你让它工作，你可以在以后改进实现。例如，您可以存储指向items 的指针，以避免复制。此外，一些typedefs 真的可以帮助澄清dp.. 的定义。重要的是首先让它使用最简单的解决方案，然后考虑这些改进。

于 2013-01-31T08:47:07.860 回答
0

您可以使用地图，一旦制作了对象，您就可以使用地图进行查询。优化算法将通过使用 HashMap 来实现。

于 2013-01-31T08:51:15.603 回答
0

使第二个向量“prev”与 dp 具有相同的尺寸。

当您为 dp[w][j] 选择最佳选项时，将前一个单元格的坐标写入 prev[w][j]

当 dp 的工作完成后，从 prev[W][n] 返回获取所有使用的单元格索引

于 2013-01-31T12:52:39.607 回答