Алгоритм псевдокода для задачи о ранце с двумя ограничениями - PullRequest
Новая
       30

Алгоритм псевдокода для задачи о ранце с двумя ограничениями

0 голосов
/ 31 марта 2019

Я пытаюсь решить следующую проблему ранца с двумя ограничениями.

Что мы знаем:

  • Элемент списка Общее количество элементов
  • Элемент списка Вес
  • Значение элемента списка
  • Элемент списка Если элемент хрупок или нет (true / false)

Ограничения:

  • Элемент списка Максимальный вес рюкзака
  • Элемент списка Максимальное количество хрупких предметов, которое может содержать рюкзак.

Может кто-нибудь дать мне несколько советов по поводу алгоритмая должен использовать, псевдокод или хорошую статью?

ОБНОВЛЕНИЕ:

Важная вещь, которую я забыл упомянуть, это то, что мне также нужно знать, какие предметы я положил в сумку.

1 Ответ

0 голосов
/ 31 марта 2019

Похоже, что модификация рюкзака решит эту проблему.

Допустим, у нас есть N предметов, максимальный вес кнесскака равен W, а максимальное количество хрупких предметов равно F

давайте определим нашеТаблица dp в виде трехмерного массива dp [N + 1] [W + 1] [F + 1]

Теперь dp [n] [w] [f] хранит максимальное значение, которое мы можем получить, заполняя рюкзакс некоторым подмножеством предметов из первых n предметов, имеющих вес точно w и имеющих точно f хрупких предметов.

frop dp [n] [w] [f] мы можем перейти в состояния:

  • dp [n + 1] [w] [f], если мы пропустим n + 1-й элемент
  • dp [n + 1] [w + weight (n + 1)] [f + isFragile(n + 1)] если мы возьмем n + 1-й элемент

, то псевдокод: 

dp[N+1][W+1][F+1] // memo table, initially filled with -1

 int solve(n,w,f)
{
    if(n > N)return 0;
    if(dp[n][w][f] != -1) return dp[n][w][f];

    dp[n][w][f] = solve(n+1,w,f); //skip item
    if(w + weight(n) <= W && f + isFragile(n) <=F)
    dp[n][w][f] = max(dp[n][w][f], value(n) + solve(n+1, w + weight(n), f + isFragile(n)));

    return dp[n][w][f]
}

print(solve(1,0,0))

Получить фактическое подмножество также не сложно: 

vector<int> getSolution(n,w,f)
{   
    int optimalValue = solve(n,w,f);
    vector<int>answer; //just some dynamic array / arrayList

    while(n <= N)
    {
        if(solve(n+1,w,f) == optimalValue)n++; //if after skipping item we can still get optimal answer we just skip it
        else //otherwise we cant so current item must be taken
        {
            int new_w = w + weight(n);
            int new_f = f + isFragile(n);
            answer.push_back(n); //so we just save its index, and update all values
            optimalValue -= value(n);
            n++;
            w = new_w;
            f = new_f;
        }
    }
    return answer;
}
...