C++蛮力背包的一部分

-10

阅读器，嗯，我觉得我刚刚脑残一点。我正在实施背包，我想过我曾经实施过1到2次蛮力算法。所以我决定再做一个。这里是我ocked英寸C++蛮力背包的一部分

让我们来决定W是最大权重，w（min）是最小加权元素，我们可以在像背包一样放k=W/w(min)次。我正在解释这一点，因为你，读者，更好地知道为什么我需要问我的问题。

现在。如果我们想象我们可以放入背包中的3种东西，而我们的背包可以存储15个单位的质量，那么让我们分别计算每个单位的重量。所以我们可以放置第一类15件东西，或第二类7件东西和第一类东西。但是像22222221[7ed]和12222222[7ed]这样的组合对我们来说意味着相同。并数它们是浪费我们支付决定的任何类型的资源。（这是一个笑话，因为如果我们有一个更便宜的算法，BF是浪费，但我很感兴趣）

正如我猜想我们需要通过所有可能的组合选择类型被称为“组合重复”。 C'(n,k)的数量计为(n+k-1)!/(n-1)!k!。我在我的理论中发现了一个洞，我们可能需要添加一个空的，零加权的零价格的物品来保存空闲空间，它可能只是增加n 1）

so ，怎么了。

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;并且必须由{0,1,2，...，n}中的k'个元素（与其中顺序不重要的重复的组合）生成为C'（n，k）（关于上面的链接）

就是这样。证明我错了或帮助我。提前非常感谢_

是的，当然算法会花费很多时间，但它看起来应该工作。我对它很感兴趣。

UPDATE：

什么我错过？

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

来源

2016-12-21 0x9093717

我不能工作了，你在问什么 –

我需要知道，如何产生rcomb（N，K）元素1在循环中一次从零到NumberOfrcomb（n，k）。 – 0x9093717

就好像我们有n = 4; （从0到3的元素）和k = 3;我如何在没有自称的功能的单个循环中生成，如 – 0x9093717

-1

答案被稔这里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; 
}

非常感谢，稔

来源

2016-12-23 15:35:02 0x9093717

C++蛮力背包的一部分

回答

相关问题