algorithm - Strange Bank(Atcoder初学者竞赛099)

Question

为了提高取款难度，某银行允许其客户在一次操作中只取下列金额之一:

1 日元(日本货币)

6日元，6^2(=36)日元，6^3(=216)日元，...

9日元，9^2(=81)日元，9^3(=729)日元，...

一共至少需要多少次操作才能取出N日元？

不允许将您提取的资金重新存入。

约束条件1≤N≤100000N为整数。

输入以下列格式从标准输入中给出:

N输出如果至少需要 x 次操作才能取出总共 N 日元，则打印 x。

示例输入 1127示例输出 14个提取1日元、9日元、36(=6^2)日元、81(=9^2)日元，分四次操作可以提取127日元。

这对我来说似乎是一个简单的贪婪问题，所以这就是我使用的方法，但我看到其中一个样本得到了不同的结果并想通了，它不会总是贪婪的。

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std;


int intlog(int base, long int x) {
return (int)(log(x) / log(base));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

long int n;cin>>n;

int result=0;
while(n>0)
{
int base_9=intlog(9,n);int base_6=intlog(6,n);
int val;
val=max(pow(9,base_9),pow(6,base_6));
//cout<<pow(9,base_9)<<" "<<pow(6,base_6)<<"\n";
val=max(val,1);
if(n<=14 && n>=12)
    val=6;
n-=val;
//cout<<n<<"\n";
result++;
}
cout<<result;
return 0;
}

在 n 14 和大于 12 时，我们必须选择 6 而不是 9，因为要达到零，需要的步数更少。

它只为 18/22 TC 提供 AC 请帮助我理解我的错误。

Answer 1

贪婪在这里不起作用，因为贪婪地选择答案，即每一步的最佳结果并不能保证最好的最终结果(你可以在你的例子中看到)。因此，您应该在每一步遍历所有可能的场景，以找出总体最优结果。

现在让我们看看我们如何做到这一点。如您所见，这里的最大输入可能是 10^5。并且我们可以在一次操作中提取以下仅有的 12 个值中的任何一个 -

[1, 6, 9, 36(=6^2), 81(=9^2), 216(=6 >^3), 729(=9^3), 1296(=6^4), 6561(=9^ 4), 7776(=6^5), 46656(=6^6), 59049(=9^5)]

因为 6^7 和 9^6 会大于 100000。

因此，在每个值为 n 的步骤中，我们将尝试从上述数组中获取每个可能的(即小于或等于 n)元素 arr[i] 和然后递归地解决 n-arr[i] 的子问题，直到我们达到零。

solve(n)
 if n==0 
  return 1;
 ans = n;
 for(int i=0;i<arr.length;i++)
   if (n>=arr[i])
     ans = min(ans, 1+solve(n-arr[i]);
 return ans;

现在这是非常耗时的递归解决方案(O(n*2^12))。我们将尝试优化它。当您尝试一些示例案例时，您会发现子问题是重叠的，这意味着可能存在重复的子问题。这就是动态规划的用武之地。您可以存储每个子问题的解决方案，以便我们将来可以重新使用它们。所以我们可以修改我们的解决方案如下

solve(n)
 if n==0 
  return 1; 
 ans = n;
 if(dp[n] is seen)
   return dp[n];
 for(int i=0;i<arr.length;i++)
   if (n>=arr[i])
     ans = min(ans, 1+solve(n-arr[i]);
 return dp[n] = ans;

DP求解的时间复杂度是O(n*12);