动态编程背包K精确项目 [英] Dynamic Programming Knapsack K-exact items
问题描述
我发现了这个非常方便的示例代码,该代码实现了背包问题的DP解决方案(对发帖人表示敬意)。
I found this very handy example code which implements a DP solution to the knapsack problem (kudos to the person who posted it).
https://codereview.stackexchange.com/questions/20569/dynamic-programming-solution-to-knapsack-问题
我正在尝试对其进行修改,以包括对背包中k项数量的限制。
I am trying to modify it to include a constraint on the number of items k in the knapsack.
我添加了第三个参数
def knapsack(items, maxweight, maxitems):
,并对重构进行了如下修改:
and modified the reconstruction as follows:
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并在重建之前考虑约束条件(我*认为这是在最佳价值评估期间)。
Provided I input enough items to choose from this will always converge to the desired k number of items. However, I am fairly certain that this is not finding the closest approximation of the global optimum. The discussions I have read after some searching refer to adding a third dimension k and accounting for the constraint before the reconstruction (I *think this would be during the best value assessment).
有人可以提供如何执行此操作的示例吗?理想情况下,一个工作正常的python示例将是很棒的,但我将接受伪代码。我已经读过一些使用符号的说明,但是我仍然不确定如何用k进行约束(除了我在这里所做的以外)。
Can someone provide an example of how to do this? Ideally a working python example would be fantastic but I'll settle for pseudocode. I have read a few instructions using notation but I am still not sure how to constrain with k (outside of what I have done here).
谢谢!
推荐答案
正如我在上面的注释中所述,第三个维度是必需的,我已经编写了一个递归动态编程解决方案:
As i stated in the comment above a third dimension is required, i have written a recursive dynamic programming solution :
#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
Link to solution on ideone : https://ideone.com/wKzqXk
这篇关于动态编程背包K精确项目的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!