背包问题中的“至少X价值”约束

Question

如何解决这个变种的背包问题？

你有n个物品（x1，...，xn），每个物品都有成本ci和价值vi（1<=i<=n），还有一个额外的限制X，它是所选项目价值的下限。 找到x1，...，xn的子集，使价值至少为X的物品的成本最小。

我试图通过动态规划来解决这个问题，我的想法是将通常使用的表格修改为K [n，c，X]，其中X是我需要达到的最小值，但似乎没有什么效果。有什么好的建议吗？

- Luca Giorgi

---

背包的大小是否有上限？ - uSeemSurprised

不，文本中没有提到任何相关信息。 - Luca Giorgi

Answer 1

想出一种方法来将问题简化为最初的背包问题。

首先，假设您已经在解决方案中包含了所有项目。您的成本是Cost_Max，实现的价值是Val_Max（应该>= X才能存在解决方案）。

现在，回想一下最初的背包问题：给定一组带有权重W（i）和价值V（i）的物品，找到权重限制为w时的最大可达值。

现在，我们将使用这个背包问题来找到所有不包含在我们答案集中的项目。

因此，在计算您的问题中的Cost_Max和Val_Max之后，您必须将：

• 成本（ci's）视为价值（即V(i)'s）
• 价值（vi's）视为重量（即W(i)'s）
• （Val_Max - X）视为重量限制w

这将为您提供可以删除的最大成本，同时您的价值仍然>= X。

因此，如果从上一步中找到的成本为Cost_Knapsack，则您的答案为Cost_Max - Cost_Knapsack。

- Avikalp Srivastava

Answer 2

这可以类似于我们解决背包问题的方式来完成，对于每个索引，我们尝试将一个值放入背包中或不放入，而这里背包的大小没有限制，因此我们可以将任意数量的元素放入背包中。

然后，我们只需要考虑那些满足“背包大小≥X”的解决方案。

背包的状态为"DP[i][j]"，其中"i"是元素的索引，"j"是当前背包的大小，注意我们只需要考虑那些具有"j≥X"的解决方案。

以下是C++中的递归动态规划解决方案:

#include <iostream>
#include <cstring>
#define INF 1000000000


using namespace std;

int cost[1000], value[1000], n, X, dp[1000][1000];

int solve(int idx, int val){
    if(idx == n){
        //this is the base case of the recursion, i.e when
        //the value is >= X then only we consider the solution
        //else we reject the solution and pass Infinity
        if(val >= X) return 0;
        else return INF;
    }
    //this is the step where we return the solution if we have calculated it previously
    //when dp[idx][val] == -1, that means that the solution has not been calculated before
    //and we need to calculate it now
    if(dp[idx][val] != -1) return dp[idx][val];

    //this is the step where we do not pick the current element in the knapsack
    int v1 = solve(idx+1, val);

    //this is the step where we add the current element in the knapsack
    int v2 = solve(idx+1, val + value[idx]) + cost[idx];

    //here we are taking the minimum of the above two choices that we made and trying
    //to find the better one, i.e the one which is the minimum
    int ans = min(v1, v2);

    //here we are setting the answer, so that if we find this state again, then we do not calculate
    //it again rather use this solution that we calculated
    dp[idx][val] = ans;

    return dp[idx][val];
}

int main(){
    cin >> n >> X;
    for(int i = 0;i < n;i++){
        cin >> cost[i] >> value[i];
    }

    //here we are initializing our dp table to -1, i.e no state has been calculated currently
    memset(dp, -1, sizeof dp);

    int ans = solve(0, 0);

    //if the answer is Infinity then the solution is not possible
    if(ans != INF)cout << solve(0, 0) << endl;
    else cout << "IMPOSSIBLE" << endl;

    return 0;
}

解决方案在 ideone 上的链接：http://ideone.com/7ZCW8z

- uSeemSurprised

---

我不确定我完全理解你的解决方案，因为我对C++不是很熟练，但它似乎是有效的。你能解释一下你在这里做什么吗？ `if(dp[idx][val] != -1) return dp[idx][val];int v = solve(idx+1, val);v = min(v, solve(idx+1, val + value[idx]) + cost[idx]);return dp[idx][val] = v;` - Luca Giorgi

@Luca Giorgi 我已经为解决方案添加了注释，以便更好地解释它，你可能想查阅“递归动态规划”以更好地理解解决方案。 - uSeemSurprised