높이가 다른 더미를 모아 놓은 경우 가능한 모든 조합을 어떻게 선택할 수 있습니까?

Question

입력 : 총 비용.

출력 : 원하는 비용을 제공하는 모든 레벨 조합.

각 스택의 모든 레벨은 다른 금액 (스택 1의 레벨 1은 스택 2의 레벨 1과 동일하지 않습니다). 나는 수동으로 (하드 코딩 된) 입력 한 기본 비용 (수준 1)에 따라 실제 비용 수준으로 변환하는 기능이 있습니다.

나는 입력 된 비용을주는 수준의 조합을 찾아야합니다. 가능한 솔루션이 여러 개 있다는 것을 알고 있지만 모든 가능성을 반복 할 수있는 방법 만 필요합니다.

는이 솔루션의 하나 입력 = 224

: 여기

는 내가 필요로 무엇

---

내가 다른 수준을 선택해야하는 간단한 프로그램을 만들고 있어요 스택을 계산 한 다음 비용을 계산하면 존재하는 모든 가능한 비용을 알아야합니다 ... 각 스택의 각 레벨마다 다른 금액의 비용이 들지만 문제는 아니지만 문제는 각 스택마다 하나의 레벨을 선택하는 것입니다 .

그래서, 모든 스택은 레벨 0, 항상 레벨 0이 있습니다

아마 아주 막연하게, 그래서 여기에 (당신은 불쌍한 내 그림 실력을 용서해야합니다) 사진 있다는 설명 비용 0 돈.

추가 정보 :

• I가 "maxLevels"라는 배열, 그 배열의 길이가 스택의 수이며, 각 요소 (예를 들어 그 스택에서 가장 높은 수준의 수 , maxLevels [0] == 2).
• 레벨 0은 전혀 중요하지 않으므로 1 레벨부터 반복 할 수 있습니다.
• 선택한 레벨은 maxLevels (길이가 같은)와 비슷한 배열 (이름 : "currentLevels")에 저장해야하지만 스택의 최대 레벨을 포함하는 대신 선택한 스택 레벨을 포함합니다 (예 : : currentLevels [3] == 2)
• 나는 C++ 프로그래밍 해요,하지만 의사뿐만 아니라 괜찮
• 이 숙제, 나는 (그것이를 위해 기본적으로의 재미를 위해 그것을하고 있어요하지 입니다.. 게임).

Answer 1

나는이 질문을 이해할 수 있는지 모르겠다. 그러나 각 st에서 하나의 항목을 선택하는 모든 가능한 조합을 살펴 보자. ACK (이 경우 3 * 1 * 2 * 3 * 1 = 18 가능성) :

void visit_each_combination(size_t *maxLevels, size_t num_of_stacks, Visitor &visitor, std::vector<size_t> &choices_so_far) { 
    if (num_of_stacks == 0) { 
     visitor.visit(choices_so_far); 
    } else { 
     for (size_t pos = 0; pos <= maxLevels[0]; ++pos) { 
      choices_so_far.push_back(pos); 
      visit_each_combination(maxLevels+1, num_of_stacks-1, visitor, choices_so_far); 
      choices_so_far.pop_back(); 
     } 
    } 
} 

당신은 코드를보다 구체적으로 만들기 위해, 각 조합에 대해 수행 할 무엇과 visitor.visit을 대체 할 수 있습니다. 배열 currentLevels 대신 벡터 choices_so_far을 사용했지만 배열과 함께 사용할 수도 있습니다.

Answer 2

제대로 이해하면 매우 간단합니다. 최소 비용은 0이며, 최대 비용은 스택의 높이의 합계입니다. 이 제한 사이의 특정 비용을 달성하려면 왼쪽부터 시작하여 목표가 달성 될 때까지 각 스택의 최대 레벨을 선택한 다음 나머지 스택에 대해 레벨 0을 선택할 수 있습니다. (목표를 오버 슛하는 경우 마지막으로 0이 아닌 스택을 조정해야 할 수도 있습니다.)

Answer 3

나는 그것을 풀 었다고 생각합니다. @Steve Jessop은 재귀를 사용할 생각을했습니다.

알고리즘 : 나는이 질문을 여러 번 다시 읽었습니다 그것을 이해하기 위해 고군분투

circ(currentStack) 
{ 
    for (i = 0; i <= allStacks[currentStack]; i ++)   
     if (currentStack == lastStack && i == allStacks[currentStack]) 
      return 0; 
     else if (currentStack != lastStack) 
      circ(++ currentStack); 
}