做题感悟:比赛时做的这道题,开始想暴力但是因为近段时间在看背包,看见这题就想到用完全背包可以解决,但是做了两个小时也没做出来,最后想暴力但是暴力错了。
解题思路:(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 ; }