具有“至少X值”的背包约束 [英] Knapsack with "at least X value" constraint

问题描述

您将如何解决背包的这种变化？

How would you go about solving this variation of Knapsack?

您有n个对象（x1，... xn），每个对象的成本为ci，值vi（ 1< = i< n）和附加约束X，它是所选项目值的下限。
找到x1，...，xn的子集，该子集可以使值至少为X的项的成本最小化。

You have n objects (x1,...xn), each with cost ci and value vi (1<=i<=n) and an additional constraint X, which is a lower bound on the value of the items selected. Find a subset of x1,...,xn that minimizes the cost of the items with a value of at least X.

我正在尝试解决这是通过动态编程实现的，我想到的是将通常使用的表修改为K [n，c，X]，其中X是我需要达到的最小值，但这似乎无济于事。有什么好主意吗？

I am trying to solve this through Dynamic Programming, and what I thought of was to modify the usual table used into K[n,c,X] where X would be the minimum value I need to reach, but that seems to bring me nowhere. Any good ideas?

推荐答案

可以像处理背包问题一样进行类似操作，在每个索引处尝试放入是否在背包内设置了一个值，并且背包的大小没有限制，因此我们可以在背包内放置任何元素。

This can be done similarly like we do the knapsack problem, at each index we try to either put in a value inside the knapsack or not, and here the knapsack has no bound on the size hence we can put any no of elements inside the knapsack.

然后，我们只需要仅考虑满足背包尺寸> = X 的那些解决方案。

Then we just need to consider only those solutions that satisfy the condition that the size of the knapsack >= X.

背包是 DP [i] [j] ，其中 i 是元素的索引，而 j 是当前背包的大小，请注意，我们只需要考虑具有 j> = X 的解决方案。

The state of the knapsack is DP[i][j] where i is the index of the element and j is the size of the current knapsack, notice we only need to consider those solutions that have j >= X.

下面是c ++中的递归动态编程解决方案：

Below is a recursive Dynamic Programming solution in 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

Link to solution on ideone : http://ideone.com/7ZCW8z

这篇关于具有“至少X值”的背包约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！