如何在递归背包中查找元素的索引？

Question

我正在尝试实现递归背包，它将 return 两件事：

我们通过填充背包获得的最大值。
考虑填充背包的元素索引。

请注意，我不想使用动态编程方法来完成此操作（通过反向迭代二维矩阵来获取元素的索引）。我想了解如何在递归背包方法中完成它？

这是我在下面尝试过的方法（得到正确的最大值（op#1）但没有得到正确的索引列表（op#2））：

int knapsack(vector<int> wt, vector<int> val, int W, int N, vector<int>& idx)
{
    if (W == 0 || N == 0) return 0;

    if (wt[N - 1] <= W)
    {
        int  consider = val[N - 1] + knapsack(wt, val, W - wt[N - 1], N - 1, idx);
        int  dontconsider = knapsack(wt, val, W, N - 1, idx);

        if (consider > dontconsider)
        {
            idx.push_back(N-1);
        }
        return max(consider, dontconsider);
    }
    else
    {
        return knapsack(wt, val, W, N - 1, idx);
    }
}
int main()
{
    vector<int> wt = { 10, 20, 30 };
    vector<int> val = { 60, 100, 120 };
    int W = 50;

    vector<int> idx; // this should retain the indexes of the elements considered for knapsack.
    cout << knapsack(wt, val, W, wt.size(), idx);
    cout << "\nIndex of elements considered for knapsack: ";
    for (int i = 0; i < idx.size(); i++)
        cout << idx[i] << " ";

    getchar();
    return 0;
}

预期输出应为：

220

考虑背包的元素索引：1 2

请帮帮我。谢谢。

Answer 1

矢量 idx 通过引用传递：vector<int>& idx。

问题在于：

int  consider = val[N - 1] + knapsack(wt, val, W - wt[N - 1], N - 1, idx);
int  dontconsider = knapsack(wt, val, W, N - 1, idx);

这个向量idx被修改了两次。

一个解决方案是为第一次调用创建一个临时向量...

#include <iostream>
#include <vector>
#include <algorithm>

int knapsack(const std::vector<int>& wt, const std::vector<int>& val, int W, int N, std::vector<int>& idx) {
    if (W == 0 || N == 0) return 0;

    if (wt[N - 1] <= W) {
        std::vector<int> idx0;
        int  consider = val[N - 1] + knapsack(wt, val, W - wt[N - 1], N - 1, idx0);
        int  dontconsider = knapsack(wt, val, W, N - 1, idx);

        if (consider > dontconsider) {
            idx = idx0;
            idx.push_back(N-1);
            return consider;
        }
        return dontconsider;
    }
    else {
        return knapsack(wt, val, W, N - 1, idx);
    }
}
int main()
{
    std::vector<int> wt = { 10, 20, 30 };
    std::vector<int> val = { 60, 100, 120 };
    int W = 50;

    std::vector<int> idx; // this should retain the indexes of the elements considered for knapsack.
    std::cout << knapsack(wt, val, W, wt.size(), idx);
    std::
    cout << "\nIndex of elements considered for knapsack: ";
    for (int i = 0; i < idx.size(); i++)
        std::cout << idx[i] << " ";
    std::cout << "\n";
    //getchar();
    return 0;
}

Answer 2

Damien 的诊断是正确的。问题是在迭代的多个评估分支中重复 idx 向量中已考虑的条目。

我只会添加一种我认为会更简单的新方法。您可以简单地更改代码，使 idx 成为一个集合对象，而不是使用向量，它是一个类似于向量的容器，但有一个重要的区别：它不允许重复的元素。因此，如果您插入一个已包含在集合中的元素，它不会添加新元素。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int knapsack(const vector<int> wt, const vector<int> val, const int W, int N, set<int>& idx)
{
    if (W == 0 || N == 0) return 0;

    if (wt[N - 1] <= W)
    {
        int  consider = val[N - 1] + knapsack(wt, val, W - wt[N - 1], N - 1, idx);
        int  dontconsider = knapsack(wt, val, W, N - 1, idx);

        if (consider > dontconsider)
        {
            idx.insert(N-1);
        }
        return max(consider, dontconsider);
    }
    else
    {
        return knapsack(wt, val, W, N - 1, idx);
    }
}
int main()
{
    vector<int> wt = { 10, 20, 30 };
    vector<int> val = { 60, 100, 120 };
    int W = 50;

    set<int> idx; // this should retain the indexes of the elements considered for knapsack.
    cout << "Maximum value obtained: " << knapsack(wt, val, W, wt.size(), idx);

    cout << "\nIndex of elements considered for knapsack: ";
    for (auto i : idx)
        cout << i << " ";
    cout << endl;

    getchar();
    return 0;
}

这是我使用集合的示例代码（请注意，我必须进行小幅调整，因为有一些方法如 pusk_back 是特定于向量的）：

如何在递归背包中查找元素的索引？

How to find indexes of elements in recursive-knapsack?

c++

knapsack-problem

recursive-datastructures

data-structures