CodeForces 189 A

题目链接~~>

做题感悟：比赛时做的这道题，开始想暴力但是因为近段时间在看背包，看见这题就想到用完全背包可以解决，但是做了两个小时也没做出来，最后想暴力但是暴力错了。

解题思路：（1）暴力：给三个数排序，因为大的数需要的总个数少，所以遍历两个大的数（两层 for 循环，已经知道两个大的数，小的数可以解出来）。

                  （2）完全背包：必须恰好装满，所以初始化很重要（背包总结），然后以个数为价值，尽量选价值多，容量为题目给的 n 。

                  （3）母函数：以后再学。

代码（暴力）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      int a[4] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int n,num,i,j ;
     
    
   

    

     

    
    

     
 while(scanf("%d%d%d%d",&n,&a[0],&a[1],&a[2])!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sort(a,a+3) ;
     
    
   

    

     

    
    

     

       num=0 ;
     
    
   

    

     

    
    

     
 for(i=n/a[1] ;i>=0 ;i--) // 遍历两个比较大的数
     
    
   

    

     

    
    

     
 for(j=n/a[2] ;j>=0 ;j--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int k=(n-i*a[1]-j*a[2])/a[0] ;
     
    
   

    

     

    
    

     
 if(i*a[1]+j*a[2]+k*a[0]==n&&k>=0&&i+j+k>num)
     
    
   

    

     

    
    

     

       num=i+j+k ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",num) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码（完全背包）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      const int INF=-99999999 ;
     
    
   

    

     

    
    

     

      int dp[4005] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int n,a[4],i,j ;
     
    
   

    

     

    
    

     
 while(scanf("%d%d%d%d",&n,&a[0],&a[1],&a[2])!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(i=1 ;i<=n ;i++) // 初始化边界
     
    
   

    

     

    
    

     

       dp[i]=INF ;
     
    
   

    

     

    
    

     

       dp[0]=0 ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<3 ;i++)  // 以个数为价值
     
    
   

    

     

    
    

     
 for(j=a[i] ;j<=n ;j++)
     
    
   

    

     

    
    

     
 if(dp[j]<dp[j-a[i]]+1)
     
    
   

    

     

    
    

     

       dp[j]=dp[j-a[i]]+1 ;
     
    
   

    

     

    
    

     
 printf("%d\n",dp[n]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/18178995