hdu 3033 I love sneakers! (多组中至少选一个的背包)

思路分析：

如果看了好多解题报告还不懂思路的话，请自己copy一份解题报告，然后在更新dp数组的前后，输出一个dp数组就可以啦~

dp【i】【j】表示前i种鞋子 j容量下的背包最多能装多少

首先要将那些永远不会到达的状态标记为-1，

也就比如说，你买第一种产品的时候，那些钱不够的状态。那么后面就更不用考虑这些状态了，因为他第一种鞋子都没买到，就更不用谈买第二种。

然后把dp【1】【1-M】标记为0 开始递推。

if(dp[t-1][j-w[index]]!=-1)
dp[t][j]=max(dp[t][j],dp[t-1][j-w[index]]+v[index]); 代表这个种类是第一次选。

if(dp[t][j-w[index]]!=-1)
dp[t][j]=max(dp[t][j],dp[t][j-w[index]]+v[index]); 代表这个种类不是第一次选。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; int dp[12][10005]; vector 
       
         S[105]; int w[105]; int v[105]; int main() { int n,W,type; while(scanf("%d%d%d",&n,&W,&type)!=EOF) { for(int i=1;i<=type;i++) S[i].clear(); for(int i=1;i<=n;i++) { int tmp; scanf("%d%d%d",&tmp,&w[i],&v[i]); S[tmp].push_back(i); } for(int i=0;i<=type;i++) { for(int j=0;j<=W;j++) { //printf("j = %d\n",j); if(i==0)dp[i][j]=0; else dp[i][j]=-1; } } for(int t=1;t<=type;t++) { for(int i=0;i
        
         =w[index];j--) { if(dp[t][j-w[index]]!=-1) dp[t][j]=max(dp[t][j],dp[t][j-w[index]]+v[index]); if(dp[t-1][j-w[index]]!=-1) dp[t][j]=max(dp[t][j],dp[t-1][j-w[index]]+v[index]); } } } if(dp[type][W]<0) printf("Impossible\n"); else printf("%d\n",dp[type][W]); } return 0; } /* 3 5 3 1 2 5 2 2 1 3 2 2 Impossible */