【算法总结】动态规划-背包问题

动态规划-背包问题

此博客分别讨论0-1背包，完全背包和多重背包，并给出相应的解题模板。

0-1背包

题目：有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。 

0-1背包问题：在最优解中，每个物品只有两种可能的情况，即在背包中或者不在背包中（背包中的该物品数为0或1），因此称为0-1背包问题。

步骤1-找子问题：子问题必然是和物品有关的，对于每一个物品，有两种结果：能装下或者不能装下。第一，包的容量比物品体积小，装不下，这时的最大价值和前i-1个物品的最大价值是一样的。第二，还有足够的容量装下该物品，但是装了不一定大于当前相同体积的最优价值，所以要进行比较。由上述分析，子问题中物品数和背包容量都应当作为变量。因此子问题确定为背包容量为j时，求前i个物品所能达到最大价值。

步骤2-确定状态：由上述分析，“状态”对应的“值”即为背包容量为j时，求前i个物品所能达到最大价值，设为dp[i][j]。初始时，dp[0][j](0<=j<=V)为0，没有物品也就没有价值。

步骤3-确定状态转移方程：由上述分析，第i个物品的体积为w,价值为v，则状态转移方程为

• j<w，dp[i][j] = dp[i-1][j] //背包装不下该物品，最大价值不变
• j>=w, dp[i][j] = max{ dp[i-1][j-list[i].w] + v, dp[i-1][j] } //和不放入该物品时同样达到该体积的最大价值比较

示例代码（具体输入输出见王道机试指南第七章）：

#include<cstdio>
int max(int a, int b)//取最大值函数
{
return a > b ? a : b;
}
struct Thing
{
int w;
int v;
}list[101];
int dp[101][1001];
int main()
{
int s, n;//背包容量和物品总数
while (scanf("%d%d", &s, &n) != EOF)
{
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &list[i].w, &list[i].v);//读入每个物品的体积和价值

}
for (int i = 0; i <= s; i++) dp[0][i] = 0;//初始化二维数组
for (int i = 1; i <= n; i++)//循环每个物品，执行状态转移方程

{
for (int j = s; j >= list[i].w; j--)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - list[i].w] + list[i].v);
}
for (int j = list[i].w - 1; j >= 0; j --)
{
 dp[i][j] = dp[i - 1][j];
}
}
printf("%dn", dp[n][s]);
}
return 0;
}

直接按照状态转移方程正序遍历j也可以，上方代码只是为了和优化算法统一。

#include<cstdio>
int max(int a, int b)//取最大值函数
{
return a > b ? a : b;
}
struct Thing
{
int w;
int v;
}list[101];
int dp[101][1001];
int main()
{
int s, n;//背包容量和物品总数
while (scanf("%d%d", &s, &n) != EOF)
{
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &list[i].w, &list[i].v);//读入每个物品的体积和价值

}
for (int i = 0; i <= s; i++) dp[0][i] = 0;//初始化二维数组
for (int i = 1; i <= n; i++)//循环每个物品，执行状态转移方程

{
for (int j = 0; j <= s; j++)
{
if (j >= list[i].w)dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - list[i].w] + list[i].v);
else dp[i][j] = dp[i - 1][j];
}
}
printf("%dn", dp[n][s]);
}
return 0;
}

变式：要求恰好装满背包时，把dp[0][0]设为0，其余dp[0][i]设为负无穷即可，这样只有恰好达到dp[n][s]时，dp[n][s]才为正值（用优化算法也可以）。

#include<cstdio>
const int INF = -999999;
int max(int a, int b)//取最大值函数
{
return a > b ? a : b;
}
struct Thing
{
int w;
int v;
}list[101];
int dp[101][1001];
int main()
{
int s, n;//背包容量和物品总数
while (scanf("%d%d", &s, &n) != EOF)
{
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &list[i].w, &list[i].v);//读入每个物品的体积和价值

}
dp[0][0] = 0;
for (int i = 1; i <= s; i++) dp[0][i] = INF;//初始化二维数组
for (int i = 1; i <= n; i++)//循环每个物品，执行状态转移方程

{
for (int j = s; j >= list[i].w; j--)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - list[i].w] + list[i].v);
}
for (int j = list[i].w - 1; j >= 0; j--)
{
dp[i][j] = dp[i - 1][j];
}
}
printf("%dn", dp[n][s]);
}
return 0;
}

优化算法：

观察状态转移方程的特点，我们发现dp[i][j]的转移只与dp[i-1][j-list[i].w]和dp[i-1][j]有关，即仅与二维数组本行的上一行有关。因此，我们可以将二维数组优化为一维数组。不过这里要注意两点：1.j<w的状态转移方程不再需要了。2.为保证每个物品只能使用一次，我们倒序遍历所有j的值，这样在更新dp[j]的时候，dp[j-list[i].w]的值尚未被修改，就不会出现一个物品重复使用的问题。

优化后的状态转移方程：dp[j] = max{ dp[j-list[i].w] + v, dp[j] }

复杂度分析：其状态数量为n*s, n为物品数量，s为背包总体积，状态转移复杂度为O(1)，所以综合时间复杂度为O(n*s)，优化后的空间复杂度仅为O(s)。

示例代码：

#include<cstdio>
int max(int a, int b)//取最大值函数
{
return a > b ? a : b;
}
struct Thing
{
int w;
int v;
}list[101];
int dp[1001];
int main()
{
int s, n;//背包容量和物品总数
while (scanf("%d%d", &s, &n) != EOF)
{
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &list[i].w, &list[i].v);//读入每个物品的体积和价值

}
for (int i = 0; i <= s; i++) dp[i] = 0;//初始化二维数组
for (int i = 1; i <= n; i++)//循环每个物品，逆序遍历j执行状态转移方程

{
for (int j = s; j >= list[i].w; j--)
{
dp[j] = max(dp[j], dp[j - list[i].w] + list[i].v);
}
}
printf("%dn", dp[s]);
}
return 0;
}

完全背包

我们扩展0-1背包问题，使每种物品的数量无限增加，便得到完全背包问题：有一个容积为 V 的背包，同时有 n 个物品，每个物品均有各自的体积 w 和价值 v，每个物品的数量均为无限个，求使用该背包最多能装的物品价值总和。

正好利用了上述0-1背包的优化算法，这时我们正序遍历j，正好可以实现每种物品的重复利用，即相当于每种物品有无限个。

#include<cstdio>
int max(int a, int b)//取最大值函数
{
return a > b ? a : b;
}
struct Thing
{
int w;
int v;
}list[101];
int dp[1001];
int main()
{
int s, n;//背包容量和物品总数
while (scanf("%d%d", &s, &n) != EOF)
{
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &list[i].w, &list[i].v);//读入每个物品的体积和价值

}
for (int i = 0; i <= s; i++) dp[i] = 0;//初始化二维数组
for (int i = 1; i <= n; i++)//循环每个物品，正序遍历j执行状态转移方程

{
for (int j = list[i].w; j <= s; j++)
{
dp[j] = max(dp[j], dp[j - list[i].w] + list[i].v);
}
}
printf("%dn", dp[s]);
}
return 0;
}

完全背包例题：POJ1384 Piggy-Bank

#include<cstdio>
int const INF = 0x7fffffff;//因为此时是求最小值，所以INF应为无穷大
int min(int a, int b){return a < b ? a : b;}//取最小值函数
struct Thing
{
int w;
int v;
}list[501];
int dp[10001];
int main()
{
int T;//测试组数
scanf("%d", &T);
int s, s1, s2, n;//硬币总重、空猪重量、满猪重量和硬币总数
while (T--)
{
scanf("%d%d", &s1, &s2);//读入空猪重量和满猪重量
s = s2 - s1;//得到硬币总重
scanf("%d", &n);//读入硬币总数
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &list[i].v, &list[i].w);//读入每个物品的价值和重量

}
dp[0] = 0;
for (int i = 1; i <= s; i++) dp[i] = INF;//初始化
for (int i = 1; i <= n; i++)//循环每个物品，正序遍历j执行状态转移方程

{
for (int j = list[i].w; j <= s; j++)
{
if (dp[j - list[i].w] != INF) dp[j] = min(dp[j], dp[j - list[i].w] + list[i].v);//如果dp[j - list[i].w]不为无穷，就可以由此状态转移而来

}
}
if (dp[s] != INF) printf("The minimum amount of money in the piggy-bank is %d.n", dp[s]);
else puts("This is impossible.");
}
return 0;
}

多重背包

多重背包问题介于 0-1 背包和完全背包之间：有容积为V的背包，给定一些物品，每种物品包含体积 w、价值 v、和数量 k，求用该背包能装下的最大价值总量。

与之前讨论的问题一样，我们可以将多重背包问题直接转化到 0-1 背包上去，即每种物品均被视为k种不同物品，对所有的物品求0-1背包。其时间复杂度为O(s*Σk_i)。

由此可见，降低每种物品的数量 ki 将会大大的降低其复杂度，于是我们采用一种更为有技巧性的拆分。将原数量为 k 的物品拆分为若干组，每组物品看成一件物品，其价值和重量为该组中所有物品的价值重量总和，每组物品包含的原物品个数分别为：为：1、2、4…k-2^c+1，其中 c 为使 k-2^c+1 大于 0 的最大整数。这种类似于二进制的拆分，不仅将物品数量大大降低，同时通过对这些若干个原物品组合得到新物品的不同组合，可以得到 0 到 k 之间的任意件物品的价值重量和，所以对所有这些新物品做 0-1 背包，即可得到多重背包的解。由于转化后的 0-1 背包物品数量大大降低，其时间复杂度也得到较大优化，为O(s*Σlog₂(k_i))。