所有问法均以01背包问题为例,问题如下: 有\(N\)种物品和一个容量为\(V\)的背包,每种物品都有无限件可用。放入第i种物品的费用是\(C_i\),价值是\(W_i\),求背包所装物体的价值最大。 基本代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| #include using namespace std; const int N=4,V=10; int F[N+1][V+1]; int C[N+1]={0,3,4,4,5}; int W[N+1]={0,4,6,6,7}; void BasicZeroOnePack() { memset(F,0,sizeof(F)); for(int i=1;i<=N;i++) { for(int v=0;v<=V;v++) { F[i][v]=F[i-1][v]; if(v>=C[i]) F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]); } } }
|
改动都是基于这个代码。
恰好装满的要求
如果要求恰好装满的话,初始化时除了\(F[0]=0\)以外,其余的F[1,…V]均设为负无穷。因为如果要求恰好装满,初始化的时候只有容量为0的背包装容量为0的物体才是合法状态,其余的状态全都不合法,用负无穷表示。
输出方案
如果需要输出方案,我们只需逆推状态转移方程,确定这个状态是由哪一个策略所推出的,从而找到上一个状态即可。可以用\(G[i,v]\)记录来自哪个状态,代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| int G[N+1][V+1]; void BasicZeroOnePackCase() { memset(F,0,sizeof(F)); for(int i=1;i<=N;i++) { for(int v=0;v<=V;v++) { F[i][v]=F[i-1][v]; G[i][v]=0; if(v>=C[i]) { F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]); if(F[i-1][v-C[i]]+W[i]>F[i-1][v]) G[i][v]=1; } } } }
|
其实不记录也可以,我们可以直接根据\(F[i][v]\)是否等于\(F[i-1][v-C[i]]+W[i]\)的值判断得到。
输出字典序最小
所谓的”字典序最小“就是按字典排序方式,1到N号物体的选择方案排列最靠前。很明显的1肯定比2靠前,也就是说我们尽量要选择前面的物体,由于我们原先的子问题”1..i个物体,背包容量j“会分解为”1…,i-1,背包容量j“和”1…i-1,背包容量j-C[i]“两个子问题并不符合字典序的假设,因为即使第i个物体服从字典序,也无法确定前i-1个物体是否服从字典序,因为1…i-1这个子问题已经被处理过了。
于是我们把循环顺序倒过来,子问题变成了“i..1个物体,背包容量j”会分解为“i-1…,1,背包容量j”和“i-1…1,背包容量\(j-C[i]\)”两个子问题,这样只要i做了服从字典序的选择,那我们只要去继续探究i-1…1这个子问题就好了。 所以我们把状态转移方程改成这样 \[ F[i,v]=\max\{F[i+1][v],F[i+1][v-C_i]+W_i\}\] 代码也只要把i逆序,i-1变成i+1即可。在输出的时候,如果\(F[i+1][v]==F[i+1][v-C_i]+W_i\)相等,尽量选加入i的策略,因为物品i必定比i+1靠前。代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| void BasicZeroOnePackDictionaryOrder() { memset(F,0,sizeof(F)); for(int i=N;i>=1;i--) { for(int v=0;v<=V;v++) { F[i][v]=F[i+1][v]; if(v>=C[i]) F[i][v]=max(F[i+1][v],F[i+1][v-C[i]]+W[i]); } } int v=V; for(int i=1;i<=N;i++) { if(F[i][v]==F[i+1][v-C[i]]+W[i]) { cout<<i<<" "; v=v-C[i]; } } cout<<endl; }
|
求方案总数
求方案总数一般只要把状态转移方程中的max改成sum,子问题定义为“可行的方案数”即可,要注意初始条件。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void BasicZeroOnePackSum() { memset(F,0,sizeof(F)); F[0][0]=1; for(int i=1;i<=N;i++) { for(int v=0;v<=V;v++) { F[i][v]=F[i-1][v]; if(v>=C[i]) F[i][v]=sum(F[i-1][v],F[i-1][v-C[i]]); } } }
|
求最优方案总数
最优方案就是总价值最大的方案。这个时候只要跟着原01背包的策略走,哪个策略好就用哪个策略的方案数,如果一样好就把2个策略的方案数相加即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| void BasicZeroOnePackBestSum() { memset(F,0,sizeof(F)); memset(G,0,sizeof(G)); G[0][0]=1; for(int i=1;i<=N;i++) { for(int v=0;v<=V;v++) { F[i][v]=F[i-1][v]; G[i][v]=G[i-1][v]; if(v>=C[i]) { F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]); if(F[i-1][v-C[i]]+W[i]>F[i-1][v]) { G[i][v]=G[i-1][v-C[i]]; } else if(F[i-1][v-C[i]]+W[i]==F[i-1][v]) { G[i][v]+=G[i-1][v-C[i]]; } } } } }
|
求第K优解
基本思想是将每个状态表示成有序队列,将状态转移方程中的max转化成有序队列的合并。\(F[i,v]\)这个有序队列是由\(F[i-1,v]\),\(F[i-1,v-C_i+W_i\)两个有序队列合并得到的。这个两个有序队列各自有自己的前K个最优解,然后两者合并得到当前的最优的K个解。 代码如下,为了节省空间使用了一维的01背包解法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| priority_queue mergeTopK(priority_queue a,priority_queue b,int W,int K) { priority_queue c; while (c.size()<K) { if(a.top()>b.top()+W) { c.push(a.top()); a.pop(); } else { c.push(b.top()+W); b.pop(); } } return c; } void ZeroOnePackTopK(int K) { priority_queue FQueue[V+1]; for(int i=0;i<=V;i++) { for(int j=1;j<=K;j++) { FQueue[i].push(0); } } for(int i=1;i<=N;i++) { for(int v=V;v>=C[i];v--) { FQueue[v]=mergeTopK(FQueue[v],FQueue[v-C[i]],W[i],K); } } while(!FQueue[V].empty()) { cout<<FQueue[V].top()<<" "; FQueue[V].pop(); } cout<<endl; }
|
参考: 1.《背包问题9讲》,https://github.com/tianyicui/pack