动态规划的背包问题
0/1 背包问题
有$N$件物品和一个容量为$V$的背包。每种物品仅有一件,可以选择放或不放。 第$i$件物品的费用是$w[i]$,价值是$c[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
设$f[i][v]$表示前$i$件物品(部分或全部)恰放入一个容量为$v$的背包可以获得的最大价值。则其状态转移方程便是:
0/1背包的空间优化
我们可以将二维数组存储优化为一维数组存储。
在每次主循环中,如果我们以$v=V…0$的逆序推$f[v]$,这样就能保证推$f[v]$时$f[v-w[i]]$保存的是状态$f[i-1][v-w[i]]$的值。
伪代码如下:
for i = 1...N
for v = V...0
f[v] = max(f[v], f[v-w[i]]+c[i]);
其中$f[v]=max(f[v],f[v-w[i]]+c[i])$便与原转移方程等价。
完全背包问题
有$N$种物品和一个容量为$V$的背包,每种物品都有无限件可用。第$i$种物品的费用是$w[i]$,价值是$c[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
令$f[i][v]$表示前$i$种物品恰放入一个容量为$v$的背包的最大价值,于是可以按照每种物品不同的策略写出状态转移方程:
完全背包问题的空间优化
完全背包的特点恰是每种物品可选无限件,所以我们可以考虑“加选一件第$i$种物品”策略。因此我们可以使用可能已选入第i种物品的子结果$f[i][v-w[i]]$,于是我们必须采用$v=0…V$的顺序循环。
伪代码如下:
for i = 1...N
for v = 0...V
f[v] = max(f[v], f[v-w[i]]+c[i]);
另一种解法:转化为0/1背包问题
考虑到第$i$种物品最多选$floor(\frac V {w[i]})$件,于是可以把第$i$种物品转化为$floor(\frac V {w[i]})$件费用及价值均不变的物品,然后求解这个0/1背包问题。
更高效的转化方法是:把第$i$种物品拆成费用为$2^kw[i]$、价值为$2^kc[i]$的若干件物品,其中$k$满足$2^kw[i]<V$。这是二进制的思想,因为不管最优策略选几件第$i$种物品,总可以表示成若干个$2^k$件物品的和。
多重背包问题
有$N$种物品和一个容量为$V$的背包。第$i$种物品最多有$n[i]$件可用,每件费用是$w[i]$,价值是$c[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
基本的方程只需将完全背包问题的方程略微一改即可,因为对于第$i$种物品有$n[i]+1$种策略:取$0$件,取$1$件……取$n[i]$件。令$f[i][v]$表示前$i$种物品恰放入一个容量为$v$的背包的最大价值,则:
循环时注意$v-k*w[i]$ 非负即可。
转化为0/1背包问题
将第$i$种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为
且k是满足$n[i]-2^k+1>0$的最大整数。
例如,如果$n[i]$为$13$,就将这种物品分成系数分别为$1,2,4,6$的四件物品。
二维背包问题
二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。
设这两种代价分别为代价1和代价2,第$i$件物品所需的两种代价分别为$a[i]$和$b[i]$。两种代价可付出的最大值(两种背包容量)分别为$V$和$U$。物品的价值为$c[i]$。
费用加了一维,只需状态也加一维即可。设$f[i][v][u]$表示前$i$件物品付出两种代价分别恰为$v$和$u$时可获得的最大价值。状态转移方程就是:
如前述方法,可以只使用二维的数组:当每件物品只可以取一次时变量$v$和$u$采用逆序的循环,当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。
物品总个数的限制
有时,“二维费用”的条件是以这样一种隐含的方式给出的:最多只能取$M$件物品。这事实上相当于每件物品多了一种“件数”的费用,每个物品的件数费用均为$1$,可以付出的最大件数费用为$M$。
Practice
附AC代码:
#include <iostream>
#include <cstdio>
using namespace std;
int v, n=0;
// i j k
int f[1001] = {0};
int max(int a, int b){
return a > b ? a : b;
}
void processTime(){
int a, b, c, d;
scanf("%d:%d %d:%d", &a, &b, &c, &d);
v = d - b + (c - a) * 60;
}
void tryItem(int cost, int value, bool inf){
if(inf){
for (int j = cost; j <= v; j++){
f[j] = max(f[j], f[j - cost]+value);
}
}else{
for (int j = v; j >= cost; j--){
f[j] = max(f[j], f[j - cost]+value);
}
}
}
void decompose(int cost, int value, int num){
int base = 1;
while(num>=base){
tryItem(cost * base, value * base, false);
num -= base;
base <<= 1;
}
if(num>0){
tryItem(cost * num, value * num, false);
}
}
int main(){
processTime();
int n;
cin >> n;
for (int i = 1; i <= n; i++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if(c==0){
tryItem(a, b, true);
}else if(c==1){
tryItem(a, b, false);
}else{
decompose(a, b, c);
}
}
int result = 0;
for (int i = 1; i <= v; i++){
result = max(result, f[i]);
}
cout << result;
return 0;
}