алгоритм — C ++ Часть рюкзака грубой силы
читатель,
Ну, я думаю, что меня просто слегка одолели.
Я внедряю рюкзак, и я думал о том, что я реализовал алгоритм перебора, как 1 или 2 раза. Поэтому я решил сделать еще один.
И вот что я прервал.
Давайте решим, что W — максимальный вес, а w (min) — минимально взвешенный элемент, который мы можем положить в рюкзак, как k=W/w(min) раз. Я объясняю это, потому что вы, читатель, лучше знаете, почему мне нужно задать свой вопрос.
Сейчас. Если мы представим, что у нас есть примерно 3 типа вещей, которые мы можем положить в рюкзак, а наш рюкзак может хранить около 15 единиц массы, давайте посчитаем вес каждой единицы как его число соответственно. таким образом, мы можем положить как 15 вещей 1-го типа, или 7 вещей 2-го типа и 1 вещь 1-го типа. но такие комбинации, как 22222221[7ed] а также 12222222[7ed] будет значить то же самое для нас. и их подсчет — пустая трата любого вида ресурсов, которые мы платим за решение. (это шутка, потому что bf — пустая трата времени, если у нас есть более дешевый алгоритм, но я очень заинтересован)
Как я полагаю, тип выбора, который мы должны пройти через все возможные комбинации, называется «Комбинации с повторениями». Номер C'(n,k) считается как (n+k-1)!/(n-1)!k!,
(В то время как я печатал свое сообщение, я только что обнаружил дыру в моей теории. Нам, вероятно, потребуется добавить пустой элемент с нулевым взвешиванием и нулевой ценой для хранения свободного места, вероятно, просто увеличивает n на 1)
Итак, в чем дело.
https://rosettacode.org/wiki/Combinations_with_repetitions
так как эта проблема хорошо описана здесь ^ я не хочу использовать стек таким образом, я хочу генерировать вариации в одном цикле, который собирается from i=0 to i<C'(n,k),
Итак, если я могу это сделать, как это работает?
we have
int prices[n]; //appear mystically
int weights[n]; // same as previous and I guess we place (0,0) in both of them.
int W, k; // W initialized by our lord and savior
k = W/min(weights);
int road[k], finalroad[k]; //all 0
int curP=curW=maxP=maxW=0;
for (int i = 0; i<rCombNumber(n,k); i++)
{
/*guys please help me to know how to generate this mask which is consists of indices from 0 to n (meaning of each element) and k is size of mask.*/
curW=0;
for (int j=0; j<k; j++)
curW+=weights[road[j]];
if (curW<W)
{
curP=0;
for (int l=0; l<k; l++)
curP+=prices[road[l]];
if (curP>maxP)
{
maxP=curP;
maxW=curW;
finalroad = road;
}
}
}
маска, дорога — это массив индексов, каждый из которых может быть равен от 0 до n; и должны быть сгенерированы как C ‘(n, k) (ссылка об этом выше) из {0, 1, 2, …, n} по k элементов в каждом выделении (комбинация с повторениями, где порядок не важен)
вот и все. докажите, что я неправ или помогите мне. Большое спасибо заранее _
и да, конечно, алгоритм займет много времени, но похоже, что он должен работать. и мне это очень интересно
ОБНОВИТЬ:
что мне не хватает?
Решение
Ответ был предоставлен Минору здесь https://gist.github.com/Minoru/745a7c19c7fa77702332cf4bd3f80f9e ,
достаточно увеличить только первый элемент, затем мы посчитаем все переносы, установим, где мы сделали перенос, и посчитаем значение сброса как максимум элементов для сброса и сброса с ним.
вот мой код:
#include <iostream>
using namespace std;
static long FactNaive(int n)
{
long r = 1;
for (int i = 2; i <= n; ++i)
r *= i;
return r;
}
static long long CrNK (long n, long k)
{
long long u, l;
u = FactNaive(n+k-1);
l = FactNaive(k)*FactNaive(n-1);
return u/l;
}
int main()
{
int numberOFchoices=7,kountOfElementsInCombination=4;
int arrayOfSingleCombination[kountOfElementsInCombination] = {0,0,0,0};
int leftmostResetPos = kountOfElementsInCombination;
int resetValue=1;
for (long long iterationCounter = 0; iterationCounter<CrNK(numberOFchoices,kountOfElementsInCombination); iterationCounter++)
{
leftmostResetPos = kountOfElementsInCombination;
if (iterationCounter!=0)
{
arrayOfSingleCombination[kountOfElementsInCombination-1]++;
for (int anotherIterationCounter=kountOfElementsInCombination-1; anotherIterationCounter>0; anotherIterationCounter--)
{
if(arrayOfSingleCombination[anotherIterationCounter]==numberOFchoices)
{
leftmostResetPos = anotherIterationCounter;
arrayOfSingleCombination[anotherIterationCounter-1]++;
}
}
}
if (leftmostResetPos != kountOfElementsInCombination)
{
resetValue = 1;
for (int j = 0; j < leftmostResetPos; j++)
{
if (arrayOfSingleCombination[j] > resetValue)
{
resetValue = arrayOfSingleCombination[j];
}
}
for (int j = leftmostResetPos; j != kountOfElementsInCombination; j++)
{
arrayOfSingleCombination[j] = resetValue;
}
}
for (int j = 0; j<kountOfElementsInCombination; j++)
{
cout<<arrayOfSingleCombination[j]<<" ";
}
cout<<"\n";
}
return 0;
}
большое спасибо, Минору
Другие решения
Других решений пока нет …