nyoj 聪明的小明

nyoj 聪明的小明

给大家推荐个靠谱的公众号程序员探索之路，大家一起加油 

#include<stdio.h>//转为01背包问题 n相当于体积m相当于数量，重要度相当于价值 
#include<string.h>
int max(int a,int b){if(a>b) return a;else return b;
}
struct node{int v,p;
}s[25];
int dp[30000];
int main(){int N;scanf("%d",&N);while(N--){memset(dp,0,sizeof(dp));int n,m,i,j;scanf("%d %d",&n,&m);for(i=1;i<=m;i++){scanf("%d %d",&s[i].v,&s[i].p);for(j=n;j>=s[i].v;j--){dp[j]=max(dp[j],dp[j-s[i].v]+s[i].p*s[i].v);}}printf("%dn",dp[n]);}return 0;
}