帶有「至少X值」限制的揹包

Question

您將如何着手解決揹包的這種變化？

您有n個對象（x1，... xn），每個對象的成本ci和值vi（1 < = i < = n）以及附加約束X，這是項目值的下限選擇。 找到x1，...，xn的一個子集，使項目的成本最小化，其值至少爲X.

我試圖通過動態規劃來解決這個問題，我想到的是修改通常的表格用於K [n，c，X]，其中X是我需要達到的最小值，但這似乎使我無處可去。任何好主意？

Answer 1

這樣做可以類似於我們做揹包問題一樣，在每個索引處我們試着在揹包裏面放一個值，這裏揹包沒有大小的限制，因此我們可以放任何揹包內的元素。

然後我們只需要考慮那些滿足條件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; 
} 

鏈接到解決方案上ideone：http://ideone.com/7ZCW8z

Answer 2

想出了一個辦法熬下來到原來的揹包問題。

首先，假設您已經在解決方案中包含所有項目。 您的成本是Cost_Max，達到的值是Val_Max（對於存在的解決方案，應該>≥X）。現在回想一下原始揹包問題：給定一組權重W（i）和值V（i）的項目，找到權重限制= w的最大可實現值。現在

，我們將使用這個揹包問題找到所有項目不在我們的答案，包括設置

所以計算Cost_Max和Val_Max在你的問題後，你要像對待：

• 成本（CI的）作爲值（即V（I）的）
• 值（ⅵ的）作爲權重（即，W（I）的）
• （Val_Max - X）作爲重量限制瓦特

這會給你，你可以刪除的最大成本，同時你的價值仍然> = X.

所以，如果從上述步驟中發現的成本Cost_Knapsack，你的答案是Cost_Max - Cost_Knapsack。