2.1 题目
有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。放入第 i 种物品
的费用是 C i ,价值是 W i 。求解:将哪些物品装入背包,可使这些物品的耗费的费用总
和不超过背包容量,且价值总和最大。
2.2 基本思路
这个问题非常类似于 01 背包问题,所不同的是每种物品有无限件。也就是从每种
物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取 0 件、取 1 件、取 2
件......直至取 ⌊V /C i ⌋ 件等许多种。
如果仍然按照解 01 背包时的思路,令 F [i, v] 表示前 i 种物品恰放入一个容量为 v
的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:
F [i, v] = max{F [i − 1, v − kCi ] + kWi | 0 ≤ kCi ≤ v}
#include <cstdio>
#include<algorithm>
#include<string.h>
#define Max(a,b) a>b?a:b
using namespace std;
int main()
{
int t;
int dp[4][10010],val[4]={0,150,200,350},vom[4]={0,150,200,350};
scanf("%d",&t);
while(t--)
{
int v;
scanf("%d",&v);
memset(dp,0,sizeof(dp));
for(int i=1;i<=3;i++)
{
for(int j=0;j<=v;j++)//v必须升序
{
for(int k=v/vom[i];k>=0;k--)//k必须降序
{
if(j-k*vom[i]>=0)
dp[i][j]=Max(dp[i-1][j],dp[i][j-k*vom[i]]+k*val[i]);
else dp[i][j]=dp[i-1][j];
}
}
}
printf("%d\n",v-dp[3][v]);
}
}
这跟 01 背包问题一样有 O(VN ) 个状态需要求解,但求解每个状态的时间已经不
是常数了,求解状态 F [i, v] 的时间是 O( C Vi ) ,总的复杂度可以认为是 O(NV ΣV/Ci ) ,是
比较大的。
将 01 背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明 01 背包
问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是要试图改进这个
复杂度。
2.4 转化为 01 背包问题求解
01 背包问题是最基本的背包问题,我们可以考虑把完全背包问题转化为 01 背包问
题来解。
最简单的想法是,考虑到第 i 种物品最多选 ⌊V /Ci ⌋ 件,于是可以把第 i 种物品转
化为 ⌊V /Ci ⌋ 件费用及价值均不变的物品,然后求解这个 01 背包问题。这样的做法完
全没有改进时间复杂度,但这种方法也指明了将完全背包问题转化为 01 背包问题的思
路:将一种物品拆成多件只能选 0 件或 1 件的 01 背包中的物品。
更高效的转化方法是:把第 i 种物品拆成费用为 Ci*2^k 、价值为 Wi*2^k 的若干件物
品,其中 k 取遍满足 Ci*2^k ≤ V 的非负整数。
这是二进制的思想。因为,不管最优策略选几件第 i 种物品,其件数写成二进制后,
总可以表示成若干个 2^k 件物品的和。这样一来就把每种物品拆成 O(log ⌊V /Ci ⌋) 件物
品,是一个很大的改进。
2.5 O(V N ) 的算法
这个算法使用一维数组,先看伪代码:
F [0..V ] ←0
for i ← 1 to N
for v ← C i to V
F [v] ← max(F [v], F [v − Ci ] + W i )
你会发现,这个伪代码与 01 背包问题的伪代码只有 v 的循环次序不同而已。
为什么这个算法就可行呢?首先想想为什么 01 背包中要按照 v 递减的次序来循环。
让 v 递减是为了保证第 i 次循环中的状态 F [i, v] 是由状态 F [i − 1, v − Ci ] 递推而来。
换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第 i 件物品”这件策略时,依据的是一个绝无已经选入第 i 件物品的子结果 F [i − 1, v − Ci ] 。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第 i 种物品”这种策略时,却正需要一个可能已选入第 i 种物品的子结果 F [i, v − Ci ] ,所以就可以并且必须采用 v递增的顺序循环。这就是这个简单的程序为何成立的道理。
值得一提的是,上面的伪代码中两层 for 循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以由另外的思路得出。例如,将基本思路中求解 F [i, v − Ci ] 的状态转移方程显式地写出来,代入原方程中,会发现该方程可以等价地变形成这种形式:
F [i, v] = max(F [i − 1, v], F [i, v − Ci ] + Wi )
2.6 小结
完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程。希望读者能
够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,
最好能够自己想一种得到这些方程的方法。
事实上,对每一道动态规划题目都思考其方程的意义以及如何得来,是加深对动态
规划的理解、提高动态规划功力的好方法。
寒冰王座
#include <cstdio>
#include<algorithm>
#include<string.h>
#define Max(a,b) a>b?a:b
using namespace std;
int main()
{
int t;
int dp[10010],val[4]={0,150,200,350},vom[4]={0,150,200,350};
scanf("%d",&t);
while(t--)
{
int v;
scanf("%d",&v);
memset(dp,0,sizeof(dp));
for(int i=1;i<=3;i++)
{
for(int j=vom[i];j<=v;j++)
{
dp[j]=Max(dp[j],dp[j-vom[i]]+val[i]);
}
}
printf("%d\n",v-dp[v]);
}
}
