题目 知识点： 背包DP 讲解： 对于这一类题有个名字叫分组背包，是九大背包之一，而这一个也不会太难，我们现在来看看。 这一题我们其实可以看做0/1背包，然后加一个每组只可以取1个的条件，我们发现如果加了这个条件，那么我们用0/1背包的做法就会有后效性，所有后效性都可以通过加状态维数来消除（个人认为，如果有反例欢迎留言），我们发现后效性和组别有关所以我们就可以这样，对于一组里面的每一个我们都枚举计算一遍，这样我们就可以保证每个答案每组最多取一个，这样这个后效性就解决了。 代码：
#include<iostream> #include<cstdio> using namespace std; struct beibao { int v,w;//v是价值，w是重量 }AC[1000]; int dp[1000],a[1000][1000],V,N,T; int main () { int ans=0; scanf("%d %d",&V,&N); for (int i=1;i<=N;i++) { int p; scanf("%d %d %d",&AC[i].w,&AC[i].v,&p); a[p][0]++;//我们用a数组存对于每一组的每一个对应的编号 a[p][a[p][0]]=i; T=max(p,T);//T表示组数，因为没告诉所以自己计算 } for(int i=1;i<=T;i++)//组数，我们放在最外围可以保证这个组里面的最多取1个 for(int j=V;j>=0;j--)//重量 for(int k=1;k<=a[i][0];k++)//从每一组第一个数开始递推 if(AC[a[i][k]].w<=j)//判断数组是否可以转移 dp[j]=max(dp[j],dp[j-AC[a[i][k]].w]+AC[a[i][k]].v); for(int i=1;i<=V;i++)//对于每个容量取最大 ans=max(ans,dp[i]); printf("%d",ans); return 0; }如果有疑问的欢迎留言。 祝大家可以AC。
