题意：有n个电影光盘，每张光盘看完需要一些花时间并且能获得一些happy值。很奇怪但是商家只愿意出售m张。并且观看得总时间有限。求能够把m张看完，并且获得最大的happy值。如果不能看完m张光盘，那就输出0。
思路：普通的01背包变形，这里有两个限制条件。一是背包体积有限，二是从n中挑选m个满足条件的。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF=1<<30; const int maxn =110; int l[maxn],v[maxn]; int dp[maxn][maxn*100]; int N,M,L; void Debug() { for(int i=0;i<=M;i++) { for(int j=0;j<=L;j++) printf("%d ",dp[i][j]); printf("\n"); } printf("\n"); } int main() { int t; // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); scanf("%d",&t); while(t--) { scanf("%d%d%d",&N,&M,&L); for(int i=0;i<N;i++) scanf("%d%d",&l[i],&v[i]); memset(dp,0,sizeof(dp)); for(int i=0;i<=M;i++) { for(int j=0;j<=L;j++) { if(i==0) dp[i][j]=0; else dp[i][j]=-INF; } } // printf("%d %d %d\n",M,N,L); // for(int i=0;i<N;i++) // printf("%d %d\n",l[i],v[i]); for(int i=0;i<N;i++) { for(int j=M;j>=1;j--) { for(int k=L;k>=l[i];k--) dp[j][k]=max(dp[j][k],dp[j-1][k-l[i]]+v[i]); // Debug(); } } if(dp[M][L]<0)dp[M][L]=0; printf("%d\n",dp[M][L]); } }