动态规划背包问题-K个相同物品

Question

我发现这个例子非常有用，它实现了一个DP解决背包问题的代码（向发布者致敬）。您可以点击以下链接查看代码：https://codereview.stackexchange.com/questions/20569/dynamic-programming-solution-to-knapsack-problem。

我试图修改它以在背包中包含物品数量 k 的限制。

我添加了一个第三个参数。

def knapsack(items, maxweight, maxitems):

并将重构修改如下：

while i > 0:

    if bestvalues[i][j] != bestvalues[i - 1][j] and len(reconstruction) < maxitems:
        reconstruction.append(items[i - 1])
        j -= items[i - 1][1]

    i -= 1

只要我提供足够数量的选择项，这将始终收敛到所需的k个项目。然而，我相当确定这并没有找到全局最优解的最接近近似值。在一些搜索后阅读的讨论中，涉及添加第三个维度k，并在重建之前考虑约束条件（我认为这将在最佳值评估期间进行）。

有人能提供如何实现这一点的示例吗？理想情况下，一个可行的Python示例会很棒，但我会满足于伪代码。我已经阅读了一些使用符号表示法的指令，但我仍然不确定如何使用k进行约束（除了我在这里做的内容）。

谢谢！

- elligottmc

---

如果您在此处发布有关如何找到全局最优解的详细信息以及几个算法链接（如果您发布特定算法和部分实现，那就更好了），那么您可能会得到更好的回应。目前，您的问题看起来像是要求我们帮助您完成作业。 - Prune

这是我正在尝试解决的实际问题。使用案例是幻想高尔夫。我在一个有薪水的联赛中，具有k个精确项目约束的背包问题非常适合帮助我选择我的团队。我发布了我的实现，它与链接中的代码完全相同，但我在这里记录了修改。就我而言，你似乎不知道答案。所以无论如何感谢你。 - elligottmc

我只是想让你知道在StackOverflow上似乎让人们失去兴趣的原因。我绝不是背包问题上的最新专家。我正在努力收集足够的了解你的情况，以决定是否是时候让我重新投入这个领域了。感谢澄清：了解边界将会有所帮助。 - Prune

好的，很公平，但我觉得交付方式有些无礼。不管怎样，我并不介意，我只是想让我的模型正常工作，并希望获得一些理解。这是我提到的一个链接，其中包含一些见解。http://cs.stackexchange.com/questions/18492/variant-of-the-knapsack-problem - elligottmc

感谢您对符号的额外帮助。我并不是有意冒犯，而是想引导您远离那个领域，以留住可能会提供帮助的人。现在我花了一点时间浏览您发送的链接...非常酷！我完全没有注意到这个因素，它使得这不再是一个简单的回溯问题。 - Prune

Answer 1

如我在上面的评论中所述，需要第三个维度。我编写了一种递归动态规划解决方案：

#include<bits/stdc++.h>

using namespace std;

int noOfItems, items[100], maxWeight, maxItems, value[100];
int dp[100][1000][100];

int solve(int idx, int currentWeight, int itemsLeft){
    if(idx == noOfItems || itemsLeft == 0) return 0;
    if(dp[idx][currentWeight][itemsLeft] != -1) return dp[idx][currentWeight][itemsLeft];
    int v1 = 0, v2 = 0;
    //try to included the current item
    if(currentWeight >= items[idx]) v1 = solve(idx+1, currentWeight-items[idx], itemsLeft-1) + value[idx];
    //exclude current item
    v2 = solve(idx+1, currentWeight, itemsLeft);
    return dp[idx][currentWeight][itemsLeft] = max(v1, v2);
}

//print the contents of the knapsack
void print(int idx, int currentWeight, int itemsLeft){
    if(idx == noOfItems || itemsLeft == 0) return;
    int v1 = 0, v2 = 0;
    if(currentWeight >= items[idx]) v1 = solve(idx+1, currentWeight-items[idx], itemsLeft-1) + value[idx];
    v2 = solve(idx+1, currentWeight, itemsLeft);
    if(v1 >= v2){
        cout << idx << " " << items[idx] << " " << value[idx] << endl;
        print(idx+1, currentWeight-items[idx], itemsLeft-1);
        return;
    }else{
        print(idx+1, currentWeight, itemsLeft);
        return;
    }
}

int main(){
    cin >> noOfItems >> maxWeight >> maxItems;
    for(int i = 0;i < noOfItems;i++) cin >> items[i] >> value[i];
    memset(dp, -1, sizeof dp);
    cout << solve(0, maxWeight, maxItems) << endl;  //prints the maximum    value that we can get from the constraints
    cout << "Printing the elements in the knapsack" << endl;
    print(0, maxWeight, maxItems);
return 0;
}

ideone 上的解决方案链接：https://ideone.com/wKzqXk

- uSeemSurprised

---

谢谢！这个实现甚至比Python的实现运行得更快。尊敬。 - elligottmc

当然，我已经做了。我想修改代码并使用我的数据进行测试。它按预期工作。再次感谢。 - elligottmc