买苹果---动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
动态规划，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;
}
*/