买苹果---动态规划

﹏ヽ暗。殇╰゛Y 2022-06-09 09:47 113阅读 0赞

## 题目描述 ##

小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

## 输入描述: ##

输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

## 输出描述: ##

输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

示例1

## 输入 ##

## 20 ##

## 输出 ##

## 3 ##

/*
    动态规划，dp[i]表示购买i个苹果所需的最小袋数。初始化为dp容器为INT_MAX（也可以自己定义一个值）。从1苹果开始遍历，
    若dp[i]为INT_MAX，表示无法购买该个数的苹果，直接开始下次循环。若dp[i]不为INT_MAX，表示该个数的苹果可以购买，
    进行动态规划求解。动态规划的转移方程为：dp[i+j] = min(dp[i]+1,dp[i+j])           //j为6或8
    dp[6] = 1
    dp[8] = 1
    */
    #include<iostream>
    #include<vector>
    using namespace std;
    #define maxVal 101
    
    int main()
      {
          int n;
          while(cin>>n)
            {
               vector<int> dp(n+1,maxVal);
               dp[6]=1;
               dp[8]=1;
               for(int i=1;i<n;i++)
                  {
                     if(dp[i]==maxVal)
                          continue;
                     else
                       {
                         if(i+6<=n)  
                            dp[i+6]=min(dp[i+6],dp[i]+1); 
                         if(i+8<=n)  
                            dp[i+8]=min(dp[i+8],dp[i]+1);
                       }
                  } 
              if(dp[n]==maxVal)
                  cout<<"-1"<<endl;
              else
                  cout<<dp[n]<<endl;
            }
      }
    
    /*常规方法：不够高效
    #include<iostream>
    using namespace std;
    
    int main()
    {
    	int n;
    	while (cin >> n)
    	{
           int maxOfx=n/6;
           int maxOfy=n/8;
           int i,j;
           for(i=maxOfy;i>=0;i--)
             {
                 for(j=0;j<=maxOfx;j++)
                   {
                       if(i*8+j*6>=n)
                           break;
                   }
                 if(i*8+j*6==n)
                     break;
             }
           if(i==-1&&j==maxOfx+1)  //如果遍历了所有的情况，没有满足条件的就输出-1
               cout<<"-1"<<endl;
           else
               cout<<i+j<<endl;
    	}
    	return 0;
    }
    */