背包九讲－问法的灵活变化
背包的问法多样，本质上还是对状态转移的求解．
目录：
- 问法一：基础
- 问法二：ｍａｘ－＞ｍｉｎ
- 问法三：输出01背包的路径，
- 问法四：输出字典序最小的最优方案＆＆同时输出路径
- 问法五：求方案总数
- 问法六：最优方案的总数
- 问法六：最优方案的总数
- 问法七：求次优解、第K优解(还不会)
问法一：基础
求解最多可以放多少件物品或者最多可以装满多少背包的空间。
这都可以根据具体问题利用前面的方程求出所有状态的值（f数组）之后得到．
问法二：ｍａｘ－＞ｍｉｎ
要求的是“总价值最小”“总件数最小”，只需简单的将上面的状态转移方程中的max改成min即可。
问法三：输出01背包的路径，
背包问题是要求一个最优值，如果要求输出这个最优值的方案
记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可
例如：uva624 CD 01背包 打印路径 解法二见下一问题
ＵＶＡ６２４01背包打印路径
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10005;
int main()
{
int m, n, cd[25], dp[maxn];
bool vis[25][maxn];
while (scanf("%d %d", &m, &n) != EOF)
{
int i, j;
for (i=1; i<=n; i++)
scanf("%d", &cd[i]);
memset(dp, 0, (m+1)*sizeof(dp[0]));
memset(vis, false, sizeof(vis));
for (i=n; i>=1; i--)
{
for (j=m; j>=cd[i]; j--)
{
if (dp[j] < dp[j-cd[i]] + cd[i])
{
dp[j] = dp[j-cd[i]] + cd[i];
vis[i][j] = true;
//printf("vis:i=%d j=%d\n",i,j);
}
}
}
for (i=1, j=dp[m]; i<=n, j>0; i++)
{
if (vis[i][j])
{
printf("%d ", cd[i]);
printf("%d %d\n", i, j);
j -= cd[i];
}
}
printf("sum:%d\n", dp[m]);
}
return 0;
}解法＆分析，
ｔｅｓｔ m=4,n=3,cd[1-3]{1,2,3}
vis[i] 1 2 3
[j]
1 1 0 0
2 0 1 0
3 0 0 1
4 1 0 1分析ｖｉｓ的数值，就是可能行走的路径，再返回来减去，则可以获取路径
问法四：输出字典序最小的最优方案＆＆同时输出路径
“字典序最小”的意思是1..N号物品的选择方案排列出来以后字典序最小
先把物品逆序排列一下，以下按物品已被逆序排列来叙述。
在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果f[i][v]==f[i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同时成立，应该按照后者（即选择了物品i）来输出方案。
#include<iostream>
using namespace std;
#ifndef SYMBOL
#define maxn 1000
#endif
int c[maxn],v[maxn];
int f[maxn]={0};
int main()
{
int n,V;
cin>>n>>V;
//先逆序，从后向前，这样有利于输出时是按照最小字典序来
for(int i=n;i>=1;i--)
{
cin>>c[i]>>v[i];
}
for(int i=1;i<=n;i++)
{
for(int j=V;j>=c[i];j--)
{
f[j]=max(f[j],f[j-c[i]]+v[i]);
}
}
for(int i=n;i>=1;i--)//这也是输出路径的一种方法
{
if(f[V]==f[V-c[i]]+v[i])//两者相同以选序号最小的情况为主
{
cout<<n-i+1<<' ';
V-=c[i];
}
}
return 0;
}问法五：求方案总数
对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品，转移方程即为
f[i][v]=sum{f[i-1][v],f[i][v-c[i]]} //当前ｉ个物品在背包ｖ的容量下，是该物品装与不装的方案数的和
初始条件f[0][0]=1。//再不装也有至少一种方案．
事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。
问法六：最优方案的总数
这里的最优方案是指物品总价值最大的方案。以01背包为例。
结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：f[i][v]意义同前述，g[i][v]表示这个子问题的最优方案的总数，则在求f[i][v]的同时求g[i][v]的伪代码如下：
for i=1..N
for v=0..V
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}//必然会决定这个物品装与不装
g[i][v]=0
if(f[i][v]==f[i-1][v])//不装则
inc(g[i][v],g[i-1][v]//如果不装，但是我的背包比之前的大，就必然会装下上次的方案数
if(f[i][v]==f[i-1][v-c[i]]+w[i])//装则
inc(g[i][v],g[i-1][v-c[i]])//同理问法七：求次优解、第K优解(还不会)
对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K。
其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。
首先看01背包求最优解的状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为v时，第k优解的值。“f[i][v]是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的方程中加了一维。显然f[i][v][1..K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。
然后原方程就可以解释为：f[i][v]这个有序队列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。有序队列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]则理解为在f[i-1][v-c[i]][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果（的前K项）储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。总的复杂度是O(NVK)。
为什么这个方法正确呢？实际上，一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取到的前K个最优值。那么，对于任两个状态的max运算等价于两个由大到小的有序队列的合并。
另外还要注意题目对于“第K优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的数没有重复的。
hdu2639 Bone Collector II（背包中第 k 大值）
Bone Collector II
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MAXN 110
#define MAXV 1010
#define MAXK 50
using namespace std;
int cost[MAXN],weight[MAXN],d[MAXV][MAXK],t1[MAXK],t2[MAXK];
int main()
{
int test,n,v,k,i,j,p;
scanf("%d",&test);
while(test--)
{
scanf("%d%d%d",&n,&v,&k);
for(i=0; i<n; i++)
scanf("%d",&weight[i]);
for(i=0; i<n; i++)
scanf("%d",&cost[i]);
memset(d,0,sizeof(d));
for(p=0; p<n; p++)//找每一个物品``
{
for(i=v; i>=cost[p]; i--)//01解法
{
for(j=1; j<=k; j++)//以往默认为第一大，所以可以不用考虑``
{
t1[j]=d[i-cost[p]][j]+weight[p];//不要想到二维费用背包，这里完全不是同一回事
t2[j]=d[i][j];//将装与不装的情况存储下来．
}
t1[j]=t2[j]=-1;//不需要排序，每次都是从大到小合并的
//这里ｊ是标志位，代表两个未合并的队列的最大区域
int x,y,z;
x=y=z=1;
while(z<=k&&(t1[x]!=-1||t2[y]!=-1))//起初我是 x<=k||y<=k;如果t1、t2的后面全是零，x和z将不会增加
{//合并部分
if(t1[x]>t2[y])//类似０１中ｍａｘ
{
d[i][z]=t1[x];
x++;
}
else
{
d[i][z]=t2[y];
y++;
}
if(d[i][z-1]!=d[i][z]) //合并,当ｚ到ｋ时，推出,注意，这里本质上还是ｆｏｒ ｖ－－＞ｃｏｓｔ的循环中
z++;
}
}
}
printf("%d\n",d[v][k]);
}
return 0;
}原创文章，转载请注明： 转载自URl-team
本文链接地址: 背包九讲－问法的灵活变化
No related posts.