蓝桥杯算法提高VIP-贪吃的大嘴 （C++代码）（动态规划）

解题思路:

注意事项:

参考代码:

#include<stdio.h>
#include<algorithm>
int m,n;
int cakeMWD[50],cakeNum[50];
int d[20001]; 
void min_mwd()
{
     for(int i=1;i<=m;++i)
     {
          d[i]=99999;
     }
     d[0]=0;
     //上面是初始化，下面三个循环是重点
     for(int i=0;i<n;++i)
     {
          for(int j=0;j<cakeNum[i];++j)
          {
               for(int z=m;z>=cakeMWD[i];--z)
               {
                    d[z]=std::min(d[z],d[z-cakeMWD[i]]+1);
               }
          }
     }
}

int main()
{
     scanf("%d %d",&m,&n);
     
     for(int i=0;i<n;++i)
     {
          scanf("%d %d",&cakeMWD[i],&cakeNum[i]);
     }
     
     min_mwd();
     
    // for(int i=0;i<=m;++i)
    // {
    //  printf("%d ",d[i]);
    //  
    // }
    
     if(d[m]==99999)
          printf("><");
     else
          printf("%d\n",d[m]);
     return 0;
}