射出气球并收集最大分数

Question

有10个气球，每个气球上都写着一些点。如果客户射出气球，他将获得等于左侧气球上的点数乘以右侧气球上的点数的分数。客户必须获得最大积分才能赢得这场游戏。什么是最高分，他应该按什么顺序射出气球才能获得最高分？

请注意，如果只有一个气球，则返回该气球上的点。

我正在试着检查所有10个！排列，以找出最大值点。有没有其他有效的方法来解决这个问题？

Answer 1

正如我在评论中所说的，使用位掩码的动态编程解决方案是可能的，我们可以做的是保留一个位掩码，其中索引为i的bit处的1表示ith气球已被拍摄，而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;
}

Answer 2

​

#include<iostream>
using namespace std;

int findleft(int arr[],int n,int j ,bool isBurst[],bool &found)

{
    if(j<=0)
    {
        found=false;
        return 1;
    }
    for(int i=j-1;i>=0;i--)
    {
        if(!isBurst[i])
        {
            return arr[i];
        }
    }
    found = false;
    return 1;

}

int findright(int arr[],int n,int j,bool isBurst[],bool &found)

{

  if(j>=n)
  {
      found = false;
      return 1;
  }
  for(int i= j+1;i<=n;i++)
  {
      if(!isBurst[i])
      {
          return arr[i];
      }
  }
  found=false;
  return 1;

}
int  calc(int arr[],int n,int j,bool isBurst[])
{
    int points =0;
    bool leftfound=true;
    bool rightfound=true;
    int left= findleft( arr, n-1, j,isBurst , leftfound);
    int right = findright( arr,n-1, j,isBurst, rightfound);
    if(!leftfound && !rightfound)
    {
        points+=arr[j];
    }
    else
    {
        points+=left*right*arr[j];
    }
    return points;


}

void maxpoints(int arr[],int n,int cp,int curr_ans,int &ans,int count,bool isBurst[])
{
    if(count==n)
    {
        if(curr_ans>ans)
        {
            ans=curr_ans;
            return;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(!isBurst[i])
        {
            isBurst[i]=true;
            maxpoints(arr,n,i,curr_ans+calc(arr,n,i,isBurst),ans,count+1,isBurst);
            isBurst[i]=false;
        }
    }
}

int main()
{
    
    int n;
    cin>>n;
    int ans=0;
    int arr[n];
    bool isBurst[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        isBurst[i]=false;
    }
    maxpoints(arr,n,0,0,ans,0,isBurst);
    cout<<ans;
    return 0;
}

​