POJ 1276 Cash Machine (完全背包问题)

题意：给出一个价值sum，然后给出n，代表n个方案，接着n对代表个数与价值，要求最接近sum，但不超过sum的价值。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; int dp[100010]; int main() { int sum ,i ,j ,k ,n; while(~scanf("%d%d",&sum,&n)){ int m[20],v[20]; for(i=1;i<=n;i++) cin>





>m[i]>>v[i]; if(sum==0){ cout<<0<
       
        =0;j--) if(dp[j]) for(k=1;k<=m[i];k++){ tem=j+k*v[i]; if(tem>sum) continue; dp[tem]=1; if(tem>MAX) MAX=tem; } cout<