分三种情况。
至少取一种 那可以直接取 或者从上一种情况来取.dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v,dp[i][k-a[j].c]+a[j].v);
至多取一种 只能从上一种情况来取 dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v);
任意取 dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v,dp[i][k-a[j].c]+a[j].v);
#include#include #define maxn 110#define INF 99999999int dp[maxn][maxn];struct node{ int v; int c;}a[maxn];int max(int x,int y){ return x>y?x:y;}int main(){ int i,j,n,m,t,s,k; while(scanf("%d%d",&n,&t)!=EOF) { memset(dp,0,sizeof(dp));//初始化为0,保证dp[1][0]=0; for(i=1;i<=n;i++) { scanf("%d %d",&m,&s); for(j=1;j<=m;j++) scanf("%d%d",&a[j].c,&a[j].v); if(s==0)//至少1 { for(k=0;k<=t;k++)//保证下一次选的时候一定选一个 dp[i][k]=-INF; for(j=1;j<=m;j++) { for(k=t;k>=a[j].c;k--) { //下面的顺序不能调换 如果dp[i-1]在前面，有可能就更新了2次，v被加了2次。 //可以考虑一下 //直接选当前的 先更新自己， dp[i][k]=max(dp[i][k],dp[i][k-a[j].c]+a[j].v); //从前一种情况来选当前的 dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v); } } } else if(s==1)//最多选一个 所以从前一种来考虑 { for(k=0;k<=t;k++) dp[i][k]=dp[i-1][k]; for(j=1;j<=m;j++) { for(k=t;k>=a[j].c;k--) { dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v); } } } else if(s==2)//任意 { for(k=0;k<=t;k++) dp[i][k]=dp[i-1][k]; for(j=1;j<=m;j++) { for(k=t;k>=a[j].c;k--) { dp[i][k]=max(dp[i][k],dp[i][k-a[j].c]+a[j].v); dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v); } } } } dp[n][t]=max(dp[n][t],-1); printf("%d\n",dp[n][t]); }}