Рюкзак с ограничением «по крайней мере 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 в ваших проблемах, вы должны относиться:

• затраты (КИ) в качестве значений (т.е. V (я) 'ы)
• значения (VI) как с весами (т.е. W (я)' ы)
• (Val_Max - Х) как предел веса ш

Это даст вам максимальную стоимость вы можете удалить, пока ваше значение остается> = X.

Так, если стоимость найдено свыше шага Cost_Knapsack, ваш ответ Cost_Max - Cost_Knapsack.