폭도 피킹 - 비용이 많이 드는 여러 항목을 무작위로 선택하여 보낼 범위를 지정하십시오.

Question

실시간 전략 게임의 임의 모드를 고려 중입니다.

이 모드에서 컴퓨터 상대방은 플레이어에게 오는 임의의 공격자 그룹 (mob)을 생성해야합니다. 각각의 가능한 공격자는 관련된 생성 비용을 가지며, 각각의 턴에는 일정한 최대량이 소비됩니다. 흥미를 없애기 위해 상대방은 항상 그 금액의 절반 이상을 소비해야합니다.

비용은 동적이지만 생성 비용은 동적이지만 느리게 변경됩니다. 주어진

void randomchoice(int N, int * selections, int * costs, int minimum, int maximum) 

같은 것을 :

I 양식의 일상을 추구하고

N = 5 (for example, I expect it to be around 20 or so) 
selections is an empty array of 5 positions 
costs is the array {11, 13, 17, 19, 23} 
minimum and maximum are 83 and 166 

반환합니다 :

가장 중요한

83 <= selection[0]*11 + selection[1]*13 + selection[2]*17 + selection[3]*19 + selection[4]*23 <= 166 

, 내가 균일하게 무작위 선택을 원하는 - 내가 시도한 모든 접근법은 대다수의 가장 큰 공격자에게서 이루어지며, 작은 공격의 "저그"는 너무 희귀하다.

C/C++ 제품군의 솔루션을 선호하지만 모든 알고리즘 힌트를 환영합니다.

Answer 1

우선 난수와 최대 숫자 사이에 임의 숫자 r을 작성하고 조금 더 간단하게하기 위해이 숫자를 비용으로 접근 해 보겠습니다. 그래서 min <= r <= max입니다.

다음으로 유닛을 파견 할 때 원하는대로 균일 한 구성표를 만드십시오. 올바르게 이해하면 다음과 같이됩니다.

A 단위의 비용이 c 인 경우 m_a = r/c은 최대로 구입할 수있는 단위의 대략적인 수입니다. 이제 우리는 다른 유형의 단위 - , C, 자체 비용, 및 m_b, m_c 등을 보유하고 있습니다. S = m_a + m_b + ...으로 보겠습니다. 0에서 S 사이의 임의의 숫자 U을 생성하십시오. 가장 작은 i을 찾아 S = m_a + ... m_i이 U보다 커야합니다. 그런 다음 유형이 i 인 단위를 만들고 단위 비용을 r에서 뺍니다. r > 0 동안 반복하십시오.

재 계산 없이는 더 효율적인 방법이 있어야하지만, 균일화 된 단어의 주어진 의미에 대해서는 일 수 있습니다. 이는 통행 할 수 있습니다.

Answer 2

진정한 유니폼? 단위 유형 수 (N = 20?)와 최대 비용 지출 비율이 비교적 적은 경우 유효한 가능성을 찾기위한 검색 공간은 매우 작으며 아마도이 것을 강제 할 수 있습니다. 자바 - 억양, 죄송합니다 (나를 위해 더 자연스러운, 포트에 쉽게해야

List<Integer> choose(int[] costs, int min, int max) { 
    List<List<Integer>> choices = enumerate(costs, min, max); 
    return choices.get(new Random().nextInt(choices.size())); 
} 

// Recursively computes the valid possibilities. 
List<List<Integer>> enumerate(int[] costs, int min, int max) { 
    List<List<Integer>> possibilities = new ArrayList<List<List<Integer>>(); 

    // Base case 
    if (costs.length == 1) { 
     for (int i = min/costs[0]; i < max/costs[0]; i++) { 
      List<Integer> p = new ArrayList<Integer>(); 
      p.add(i); 
      possibilities.add(p); 
     } 
     return possibilities; 
    } 

    // Recursive case - iterate through all possible options for this unit, recursively find 
    // all remaining solutions. 
    for (int i = 0; i < max/costs[0]; i++) { 
     // Pythonism because I'm lazy - your recursive call should be a subarray of the 
     // cost array from 1-end, since we handled the costs[0] case here. 

     List<List<Integer>> partial = enumerate(costs[1:], min - (costs[0] * i), max - (costs[0] * i)); 
     for (List<Integer> li : partial) { 
      possibilities.add(li.add(0, i)); 
     } 
    } 

    return possibilities; 
}