这里有一道非常典型的题目：
链接戳这里☞：
P1064金明的预算方案
下面是源代码：
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
struct sd{
int weight,value;
bool prime;
}thing;
int M[320005];
int num=0;
bool judger[320005];
vector<sd> subject[80];//subject是指刚刚进入分组时的物品
vector<sd> group[80];//进行后续分组背包时的所用的数组
int m,n;
void init();
int main()
{
init();
int limit=0;
for(int i=1;i<=num;++i)
{
for(int k=limit;k>=0;--k)
{
for(int j=group[i].size()-1;j>=0;--j)
{
if((k==0||M[k]!=0)&&k+group[i][j].weight<=m)
{
if(!judger[k]&&M[k+group[i][j].weight]<M[k]+group[i][j].value)
{
M[k+group[i][j].weight]=M[k]+group[i][j].value;
judger[k+group[i][j].weight]=true;
}
}
if(k+group[i][j].weight>limit)
limit=k+group[i][j].weight;
}
}
memset(judger,false,sizeof(judger));
}
long long ans=0;
for(int i=0;i<=m;++i)
if(ans<M[i])
ans=M[i];
cout<<ans;
return 0;
}
void init()
{
int a,b;
int c;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&a,&b,&c);
thing.value=a*b;
thing.weight=a;
if(c==0)
{
thing.prime=true;
subject[i].push_back(thing);
}
else
{
thing.prime=false;
subject[c].push_back(thing);
}
}
for(int i=1;i<=n;++i)
{
if(subject[i].size()==0)
continue;
else
{
num++;
if(subject[i].size()==1)
{
group[num].push_back(subject[i][0]);
}
else if(subject[i].size()==2)
{
int king;
if(subject[i][0].prime) king=0; else king=1;
group[num].push_back(subject[i][king]);
sd change;
change.weight=subject[i][king].weight+subject[i][1-king].weight;
change.value=subject[i][king].value+subject[i][1-king].value;
group[num].push_back(change);
}
else if(subject[i].size()==3)
{
int king;
if(subject[i][0].prime) king=0; else if(subject[i][1].prime) king=1; else king=2;
group[num].push_back(subject[i][king]);
sd swp;
swp=subject[i][king];
subject[i][king]=subject[i][0];
subject[i][0]=swp;
sd change;
change.weight=subject[i][0].weight+subject[i][1].weight;
change.value=subject[i][0].value+subject[i][1].value;
group[num].push_back(change);
change.weight=subject[i][0].weight+subject[i][2].weight;
change.value=subject[i][0].value+subject[i][2].value;
group[num].push_back(change);
change.weight=subject[i][0].weight+subject[i][1].weight+subject[i][2].weight;
change.value=subject[i][0].value+subject[i][1].value+subject[i][2].value;
group[num].push_back(change);
}
}
}
}
其实说实话，有依赖的背包问题和分组背包问题没有什么太大的区别，最主要的区别就是我们在进行分组背包前要先进行一次01背包（但是在代码里我并没有这样实现，因为我嫌有一点麻烦，所以我用的强压的方式，把每一种方案枚举出来）。后面就和分组背包的思路是一样的了！
但是这里有一个分组背包以前没有讲到的东西······
下面重点来了！！！
Question：为什么分组背包的limit循环和后面的一个循环组内背包的循环不能反着写啊？
这个问题非常的important啊！我和我的同学谈论了一会儿，终于得出了答案！
为了理解的方便，这里我们采用画图的方式进行表达！
1、（错误情况）先循环物品，再循环背包
会出现的bug是，我们同组先扔进去的物品会对后面扔进去的物品产生影响，怎么说呢？见下图：
A:12-------扔入v=7------→B:18
()()()()()()()()()()()()()()
|________________________↑
↑
judger[B]=false
我们可以发现如果在A扔入7那么B点就为19>18,所以此时B点按常理就会自动更新然后把judger变为true，从而对他进行维护。于是此时就为下图：
A:12-------扔入v=7------→B:18
↓judger[B]=true;
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()
|____________________________↑
本来是可以在这里扔入物品2
到达C点的，可是~~~
judger[B]=true
于是我们成功的发现就这样，我们就少考虑了一种情况（注意：此情况应该是加上原来的B点位置的值，即judger一来没有被标记为true的时候），于是在这种少考虑的情况的情况下，很容易就WA掉了几个点。
2、正确情况为什么就是正确的呢？
因为第二种情况可以有效的避免出现少考虑情况的问题，在我们对一个背包中的点扔同一组的东西时，我们可以保证带有true标记的judger一定是在这个点后面的，所以不会对前面的点造成影响（相当于为了公平起见，我们这些点都是同时的扔入背包中同一个位置，如果先让一个点把背包扔一遍，实际上是很不公平的！）
下面放一些图方便理解：
错误的扔法：
step1：
A:12-------扔入v=7------→B:18
()()()()()()()()()()()()()()
|________________________↑
↑
judger[B]=false
step2：
A:12-------扔入v=7------→B:18
↓judger[B]=true;
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()
|————————————|—————————————|____________________________↑
△ 本来是可以在这里扔入物品2
到达C点的，可是~~~
judger[B]=true
相信大家在仔细看了这两幅图后，都应该明白了，有△的地方就存在被同一组前一个物品修改的可能！！！因为被修改了原来的值，所以judger变为true然后就少考虑情况了！！！而如果是正确的话（即for循环没有写反）那么△的地方就不会存在一来就被某个物品修改的情况，所以不会WA！！！
相信大家认真阅读后，应该都可以完全理解！
谢谢采纳！！！