0


【动态规划】C++ 算法458:可怜的小猪

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总 数学

力扣458:可怜的小猪

有 buckets 桶液体,其中 正好有一桶 含有毒药,其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药,你可以喂一些猪喝,通过观察猪是否会死进行判断。不幸的是,你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下:
选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水,并且该过程不需要时间。
小猪喝完水后,必须有 minutesToDie 分钟的冷却时间。在这段时间里,你只能观察,而不允许继续喂猪。
过了 minutesToDie 分钟后,所有喝到毒药的猪都会死去,其他所有猪都会活下来。
重复这一过程,直到时间用完。
给你桶的数目 buckets ,minutesToDie 和 minutesToTest ,返回 在规定时间内判断哪个桶有毒所需的 最小 猪数 。
示例 1:
输入:buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出:5
示例 2:
输入:buckets = 4, minutesToDie = 15, minutesToTest = 15
输出:2
示例 3:
输入:buckets = 4, minutesToDie = 15, minutesToTest = 30
输出:2
提示:
1 <= buckets <= 1000
1 <= minutesToDie <= minutesToTest <= 100

动态规划

dp[i][j] 表示i只小猪,j回合能发现buckets 桶液体中的毒药。

一只小猪

一回合小猪只能喝一桶,如果同时喝两桶,结果没出来,猪没了。也就是极端情况下:一回合排除一桶。
dp[1][j] = j+1 注意 j为0时,也是符合的。

两只小猪

一回合第一桶药,两头小猪喝;第二桶药,第一头小猪喝;第三桶药,第二头只小猪喝;第四桶药不喂给小猪。如果两只小猪都死了,第一桶药有毒;如果第一头小猪死了,第二桶有毒;如果第二头小猪死了,第三桶有毒;两只小猪都没死,第四桶有毒。===>>> dp[2][1] = 4二回合两头小猪都喂,如果有毒,小猪变成0只,dp[0][1] ; 只喂第一头小猪,如果有毒,猪变成一头 dp[1][1];同理,只喂第二头小猪类似:dp[1][1];不喂任何小猪的液体,两头猪:dp[2][1]。故结果为:dp[0][1] + dp[1][1]+dp[2][1] = 1 + 2 + 2 +4

总结i头猪j回合

喂所有猪的液体dp[0][j-1]喂i-1头猪的液体C

         i 
        
        
        
          i 
         
        
          − 
         
        
          1 
         
        
       
      
     
       ^{i-1}_{i} 
      
     
   ii−1​ *dp[1][j-1]喂i-2头猪的液体C 
    
     
      
       
        
       
         i 
        
        
        
          i 
         
        
          − 
         
        
          2 
         
        
       
      
     
       ^{i-2}_i 
      
     
   ii−2​*dp[2][j-1]…喂1头猪的液体C 
    
     
      
       
        
       
         i 
        
       
         1 
        
       
      
     
       ^1_i 
      
     
   i1​*dp[i-1][j-1]喂0头猪的液体C 
    
     
      
       
        
       
         i 
        
       
         0 
        
       
      
     
       ^0_i 
      
     
   i0​*dp[i][j-1]

喂k头猪液体的最大数量为:C

      i 
     
    
      k 
     
    
   
  
    ^k_i 
   
  
ik​*dp[i-k][j-1]

故dp[i][j] = Sum

       [ 
      
     
       0 
      
     
       , 
      
     
       i 
      
     
       ] 
      
     
    
      k 
     
    
   
  
    ^k_{[0,i]} 
   
  
[0,i]k​C 
 
  
   
    
     
    
      i 
     
    
      k 
     
    
   
  
    ^k_i 
   
  
ik​*dp[i-k][j-1]

空间复杂度: O(mn) m是回合数,不超过100,n是小猪数,不超过1000。
计算一种状态的时间复杂度是:O(n)
故总的时间复杂度 是O(nnm),这是理论值。刚刚超时,实际上不会。
当m等于1时,n=10。 就算1000桶,一回合,也只要10只小猪。所以n的最大值是10,不是1000。

代码

核心代码

classCCombination{public:CCombination(){
        m_v.assign(1,vector<int>());}intGet(int sel,int total){while(m_v.size()<= total){int iSize = m_v.size();
            m_v.emplace_back(iSize +1,1);for(int i =1; i < iSize; i++){
                m_v[iSize][i]= m_v[iSize -1][i]+ m_v[iSize -1][i-1];}}return m_v[total][sel];}protected:
    vector<vector<int>> m_v;};classSolution{public:intpoorPigs(int buckets,int minutesToDie,int minutesToTest){constint iTurn = minutesToTest / minutesToDie;
        CCombination com;
        vector<vector<int>>dp(1,vector<int>(iTurn+1,1));while(dp.back().back()< buckets){constint iPigNum = dp.size();
            dp.emplace_back(iTurn +1,1);auto& v = dp.back();for(int i =1; i <= iTurn; i++){
                v[i]=0;for(int k =0; k <= iPigNum; k++){
                    v[i]+= com.Get(k,iPigNum)* dp[iPigNum - k][i -1];}}}return dp.size()-1;}};

测试用例

template<classT>voidAssert(const T& t1,const T& t2){assert(t1 == t2);}template<classT>voidAssert(const vector<T>& v1,const vector<T>& v2){if(v1.size()!= v2.size()){assert(false);return;}for(int i =0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}intmain(){int buckets =1000, minutesToDie =15, minutesToTest;{
        Solution sln;
        buckets =1000, minutesToDie =15, minutesToTest =60;auto res = sln.poorPigs(buckets, minutesToDie, minutesToTest);Assert(5, res);}{
        Solution sln;
        buckets =4, minutesToDie =15, minutesToTest =15;auto res = sln.poorPigs(buckets, minutesToDie, minutesToTest);Assert(2, res);}{
        Solution sln;
        buckets =4, minutesToDie =15, minutesToTest =30;auto res = sln.poorPigs(buckets, minutesToDie, minutesToTest);Assert(2, res);}}

2023年1月版

class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
vector p;
p.push_back(1);
for (int i = 1; i <= 10; i++)
{
p.push_back(i*p[i - 1]);
}
vector<vector> dp;
dp.assign(11, vector(minutesToTest / minutesToDie + 1,1));
if (buckets <= 1)
{
return 0;
}
for (int i = 1; i <= 10; i++)
{
for (int j = 1; j <= minutesToTest / minutesToDie; j++)
{
int iSum = 0;
for (int k = 0; k <= i; k++)
{
iSum += dp[k][j - 1] * (p[i] / p[k] / p[i - k]);
}
dp[i][j] = iSum;
}
if (dp[i].back() >= buckets)
{
return i;
}
}
return 10;
}
};

2023年6月版

class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
const int iMaxTestNum = minutesToTest / minutesToDie;
//10只猪一轮,可以搞定1024 桶。所以10只猪够用了
const int iMaxPig = 10;
vector<vector> vCom(iMaxPig + 1, vector(iMaxPig + 1, 1));//组合
{
for (int i = 1; i <= iMaxPig; i++)
{
for (int j = 1; j < i; j++)
{//从i个小猪中选择j个的可能
vCom[i][j] = vCom[i - 1][j - 1] + vCom[i-1][j];
}
}
}
vector<vector> dp(iMaxTestNum + 1, vector(iMaxPig + 1, 1));
for (int i = 1; i <= iMaxTestNum; i++)
{
for (int j = 1; j <= iMaxPig; j++)
{
int iSum = 0;
for (int k = 0; k <= j; k++)
{
iSum += vCom[j][k] * dp[i - 1][j - k];
}
dp[i][j] = iSum;
}
}
for (int i = 0; i <= iMaxPig; i++)
{
if (dp[iMaxTestNum][i] >= buckets)
{
return i;
}
}
return -1;
}
};

2023年8月版

class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int iStep = minutesToTest / minutesToDie;
int iCanFindBucket = 1;
for (int pig = 0; ; pig++)
{
if (iCanFindBucket >= buckets)
{
return pig;
}
iCanFindBucket *= (iStep + 1);
}
return 0;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+

+17**
如无特殊说明,本算法用**C++**实现。

标签: 动态规划 算法 c++

本文转载自: https://blog.csdn.net/he_zhidan/article/details/135463157
版权归原作者 闻缺陷则喜何志丹 所有, 如有侵权,请联系我们删除。

“【动态规划】C++ 算法458:可怜的小猪”的评论:

还没有评论