开心的金明 （C++代码）

解题思路:

注意事项:

     直接递归会超时，用上状态转移

参考代码:

#include<bits/stdc++.h>
using namespace std;
const  int N = 25;
int value[N],weigth[N];

int dp(int total,int num)
{
 if(total < value[num])
 {
  if(num > 0)
   return dp(total,num-1);
  else
   return 0;
 }
 if(num == 0)
  return (weigth[num] * value[num]);
 if(total >= value[num])
 {
  int A = dp(total - value[num],num - 1)+weigth[num] * value[num];
  int B = dp(total,num - 1);
  return max(A,B);
 }
}

int main()
{
 int total,num;
 cin>>total>>num;
 for(int i = 0;i < num;i++)
 {
  cin>>value[i]>>weigth[i];
 }
 cout<<dp(total,num-1);
 return 0;
}