C++ Part of brute-force knapsack

Question

reader, Well, I think I just got brainfucked a bit. I'm implementing knapsack, and I thought about I implemented brute-force algorithm like 1 or 2 times ever. So I decided to make another one. And here's what I chocked in.

Let us decide W is maximum weight, and w(min) is minimal-weighted element we can put in knapsack like k=W/w(min) times. I'm explaining this because you, reader, are better know why I need to ask my question.

Now. If we imagine that we have like 3 types of things we can put in knapsack, and our knapsack can store like 15 units of mass, let's count each unit weight as its number respectively. so we can put like 15 things of 1st type, or 7 things of 2nd type and 1 thing of 1st type. but, combinations like 22222221[7ed] and 12222222[7ed] will mean the same for us. and counting them is a waste of any type of resources we pay for decision. (it's a joke, 'cause bf is a waste if we have a cheaper algorithm, but I'm very interested)

As I guess the type of selections we need to go through all possible combinations is called "Combinations with repetitions". The number of C'(n,k) counts as (n+k-1)!/(n-1)!k!. (while I typing my message I just spotted a hole in my theory. we will probably need to add an empty, zero-weighted-zero-priced item to hold free space it's probably just increases n by 1)

so, what's the matter.

https://rosettacode.org/wiki/Combinations_with_repetitions

as this problem is well-described up here^ I don't really want to use stack this way, I want to generate variations in single cycle, which is going from i=0 to i<C'(n,k).

so, If I can make it, how it works? 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 -- is an array of indices, each can be equal from 0 to n; and have to be generated as C'(n,k) (link about it above) from { 0, 1, 2, ... , n } by k elements in each selection (combination with repetitions where order is unimportant)

that's it. prove me wrong or help me. Much thanks in advance _

and yes, of course algorithm will take the hell much time, but it looks like it should work. and I'm very interesting in it.

UPDATE:

what do I miss?

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

Answer 1

The answer was provided by Minoru here https://gist.github.com/Minoru/745a7c19c7fa77702332cf4bd3f80f9e , it's enough to increment only the first element, then we count all of the carries, set where we did a carry and count reset value as the maximum of elements to reset and reset with it.

here's my code:

#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;
}

thanks a lot, Minoru