二维背包
#include<stdio.h> #include<string.h> #include<stdlib.h> int max(int a,int b) { if(a>b)return a; return b; } struct op { int v,w; }p[120]; int main() { int i,j,L,n,m,dp[120][1020],t,k; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&L); for(i=0;i<n;i++) scanf("%d%d",&p[i].v,&p[i].w); memset(dp,-1,sizeof(dp)); for(j=0;j<=L;j++) dp[0][j]=0; for(i=0;i<n;i++) { for(k=m;k>=1;k--) { for(j=L;j>=p[i].v;j--) { if(dp[k-1][j-p[i].v]==-1)break; dp[k][j]=max(dp[k][j],dp[k-1][j-p[i].v]+p[i].w); } } } if(dp[m][L]==-1) printf("0\n"); else printf("%d\n",dp[m][L]); } return 0; }