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