Стрелять воздушными шарами и собирать максимальные очки

Question

Есть 10 воздушных шаров, и каждый воздушный шар имеет на нем какую-то точку. Если клиент стреляет в воздушный шар, он получит очки, равные точкам на левом шаре, умноженному на очки на правом шаре. Клиент должен собрать максимум очков, чтобы выиграть эту игру. Какими будут максимальные баллы и в каком порядке он должен стрелять воздушными шарами, чтобы получить максимальные очки?

Обратите внимание, что если есть только один воздушный шар, вы возвращаете точки на этом воздушном шаре.

Я пытаюсь проверить все 10! перестановки, чтобы узнать максимальные точки. Есть ли другой способ эффективно решить эту проблему?

Answer 1

Как я сказал в комментариях Динамическое решение программирования с bitmasking возможно, что мы можем сделать, это сохранить битовую маску, где 1 на bit индексируется в i означает, что ith Baloon был снят, и 0 говорит, что он не был расстрелян.

Таким образом, требуется состояние динамического программирования только маски, где в каждом состоянии мы можем перейти к следующему состоянию, итерации по всем баллонам, которые не были сняты, и попытаться снять их, чтобы найти максимум.

Сложность времени такого решения будет: O((2^n) * n * n), а сложность пространства будет O(2^n).

код в C++, не отлажена вам может понадобиться отладить:

int n = 10, val[10], dp[1024]; //set all the values of dp table to -1 initially 

int solve(int mask){ 
    if(__builtin_popcount(mask) == n){ 
     return 0; 
    } 
    if(dp[mask] != -1) return dp[mask]; 

    int prev = 1, ans = 0; 
    for(int i = 0;i < n;i++){ 
     if(((mask >> i) & 1) == 0){ //bit is not set 
      //try to shoot current baloon 
      int newMask = mask | (1 << i); 
      int fwd = 1; 
      for(int j = i+1;j < n;j++){ 
       if(((mask >> j) & 1) == 0){ 
        fwd = val[j]; 
        break; 
       } 
      } 
      ans = max(ans, solve(newMask) + (prev * fwd)); 
      prev = val[i]; 
     } 
    } 
    return dp[mask] = ans; 
}