具有 "at least X value" 约束条件的背包

Question

你会如何解决背包的这个变体？

您有 n 个对象 (x1,...xn)，每个对象的成本 ci 和值 vi (1<=i<=n) 以及一个附加约束 X，它是所选项目的价值。找到 x1,...,xn 的一个子集，它可以最小化价值至少为 X 的项目的成本。

我试图通过动态规划来解决这个问题，我想到的是修改通常用于 K[n,c,X] 的 table，其中 X 是我需要的最小值到达，但这似乎让我无处可去。有什么好的想法吗？

Answer 1

这可以像我们处理背包问题一样来完成，在每个索引处我们尝试在背包内放入一个值或不放入一个值，这里背包的大小没有限制因此我们可以放任何 no背包内的元素。

那么我们只需要考虑那些满足size of the knapsack >= 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;
}

Link 到 ideone 上的解决方案：http://ideone.com/7ZCW8z

Answer 2

想出了一种方法将其归结为原始背包问题。

首先，假设您已将所有项目包含在您的解决方案中。您的成本是 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。

具有 "at least X value" 约束条件的背包

Knapsack with "at least X value" constraint

algorithm

knapsack-problem

dynamic-programming