C++ Часть ранец грубой силы

Question

читатель, Ну, я думаю, что меня просто убьют. Я реализую рюкзак, и я думал о том, что я применил алгоритм грубой силы, как 1 или 2 раза. Поэтому я решил сделать еще один. И вот что я вбил.

Решим, что W - максимальный вес, а w (min) - элемент с минимальным весом, мы можем положить в рюкзак, как k=W/w(min) раз. Я объясняю это, потому что вы, читатель, лучше знаете, почему мне нужно задать свой вопрос.

Теперь. Если мы представим себе, что у нас есть три типа вещей, которые мы можем положить в рюкзак, а наш рюкзак может хранить как 15 единиц массы, давайте считать каждый вес единицы его номером соответственно. поэтому мы можем поместить как 15 вещей 1-го типа, или 7 вещей 2-го типа и 1 вещь 1-го типа. но такие комбинации, как 22222221[7ed] и 12222222[7ed], будут одинаковыми для нас. и подсчет их - это трата любых ресурсов, которые мы платим за решение. (это шутка, потому что bf - это отходы, если у нас более дешевый алгоритм, но мне очень интересно)

Как я думаю, тип выбора, который нам нужно пройти через все возможные комбинации, называется «Комбинации с повторениями» ». Число C'(n,k) считается (n+k-1)!/(n-1)!k!. (пока я печатаю свое сообщение, я просто заметил дыру в моей теории. Нам, вероятно, нужно будет добавить пустой элемент с нулевым весом-нулевым значением, чтобы удержать свободное пространство, вероятно, просто увеличивается на 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; 

} 

} 

} 

mask, road - это массив показателей, каждый из которых может быть равен от 0 до n; и должны быть сгенерированы как C '(n, k) (ссылка об этом выше) из {0, 1, 2, ..., n} по k элементам в каждом выборе (комбинация с повторениями, где порядок несуществен)

вот и все. доказать мне неправду или помочь мне. Заранее спасибо _

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

UPDATE:

что мне не хватает?

http://pastexen.com/code.php?file=EMcn3F9ceC.txt

Answer 1

Ответ был предоставлен Minoru здесь 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; 
} 

Большое спасибо, Minoru