python - 动态规划背包 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 并在重建之前考虑约束(我*认为这将是在最佳值(value)评估期间)。

有人可以举例说明如何做到这一点吗？理想情况下，一个有效的 python 示例会很棒，但我会接受伪代码。我已经阅读了一些使用符号的说明，但我仍然不确定如何使用 k 进行约束(除了我在这里所做的之外)。

谢谢!

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