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

解题思路:0/1背包

注意事项:

参考代码:

#include<iostream>

#include<string.h>

using namespace std;

#define N 30000

#define M 25

int dp[M][N];

int n,m;//n为总钱数，m为希望购买的物品个数 

int value[M];

int w[M];

int Knapsack()

{

for(int i=0;i <= n;i++)dp[0][i]=0;

for(int i=0;i <= m;i++)dp[i][0]=0;

for(int i=1;i <= m;i++)

{

for(int j=1;j <= n;j++)

{

if(j < value[i])

{

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

} 

else

{

dp[i][j]=max(dp[i-1][j],value[i]*w[i]+dp[i-1][j-value[i]]);

}

}

}

return dp[m][n];

}

int main() 

{

cin>>n>>m;

for(int i=1;i <= m;i++)cin>>value[i]>>w[i];

cout<<Knapsack()<<endl;

return 0;

}