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

Я думал,

Я хотел сделать вариацию на тему проблемы рюкзака.

Представьте себе первоначальную проблему с предметами с различным весом / стоимостью.

Моя версия, наряду с нормальными весами/значениями, будет содержать значение «группы».

напр. Пункт1[5кг, $600, электронный] Item2[1kg, $50, food]

Теперь, имея набор таких предметов, как бы я закодировать задачу рюкзака, чтобы убедиться, что выбран максимум 1 элемент из каждой «группы».

Примечания:

1. Вам не нужно выбирать элемент из этой группы
2. В каждой группе есть несколько элементов
3. Вы по-прежнему минимизируете вес, максимизируя значение
4. Количество групп предопределено вместе с их значениями.

На данном этапе я просто пишу черновик кода и решил использовать динамический подход. Я понимаю идею, лежащую в основе динамического решения для обычной проблемы рюкзака, как мне изменить это решение, чтобы включить эти «группы»?

KnapSackVariation(v,w,g,n,W)
{
  for (w = 0 to W)
     V[0,w] = 0;
  for(i = 1 to n)
     for(w = 0 to W)
        if(w[i] <= w)
           V[i,w] = max{V[i-1, w], v[i] + V[i-1, w-w[i]]};
        else
           V[i,w] = V[i-1, w];
     return V[n,W];
}

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