解题思路:
注意事项:
直接递归会超时,用上状态转移
参考代码:
#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;
}
0.0分
0 人评分