- #include<bits/stdc++.h>
- using namespace std;
- int N,m;
- int cost[30],value[30];
- int dp[30005];
- int main(){
- memset(dp,0,sizeof(dp));
- cin>>N>>m;
- for(int i=0;i<m;i++){
- cin>>cost[i]>>value[i];
- value[i]*=cost[i];
- }
- for(int i=0;i<m;i++){
- for(int j=N;j>=cost[i];j--){
- dp[j]=max(dp[j],dp[j-cost[i]]+value[i]);
- }
- }
- cout<<dp[N];
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2867997.html