开心的金明 （C++代码）（DP动态规划，01背包问题）

解题思路:

注意事项:

参考代码:

#include<stdio.h>
#include<algorithm>
int main()
{
     int money,m;
     scanf("%d %d",&money,&m);
     int v[m+1],p[m+1];
     for(int i=1;i<=m;++i)
     {
          scanf("%d %d",&v[i],&p[i]);
     }
     int dp[m+1][money+1];
     
     for(int i=0;i<=m;++i)dp[i][0]=0;
     for(int i=0;i<=money;++i)dp[0][i]=0;
     
     for(int i=1;i<=m;++i)
     {
          for(int j=1;j<=money;++j)
          {
               if(j<v[i])
               {
                    dp[i][j]=dp[i-1][j];
               }
               else
               {
                    dp[i][j]=std::max(dp[i-1][j],(v[i]*p[i]+dp[i-1][j-v[i]]));
               }
          }
     } 
     printf("%d\n",dp[m][money]);
     return 0;
}