1103开心的金明(dp动态规划）

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

const int S = 28;

int M;//拥有的钱

int N;//需要买的物品数

int arr[S];//存价格

int brr[S];//存重要程度

int dp[30005];//这里不是S，而是自己拥有的钱的最大数，如果开辟成S的话，会运行出错

int main()

{

cin >> M >> N;

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

{

cin >> arr[i] >> brr[i];

}

for (int i = 1; i <= N; i++)//第几个家具

{

for (int j = M; j >= arr[i]; j--)//剩余的钱，钱够就放

{

dp[j] = max(dp[j], dp[j -arr[i]] +arr[i]*brr[i]);

}

}

cout << dp[M];

return 0;

}