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;
}