动态规划

一、01背包问题

 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

解题思路：状态转移方程便是：

ans[i][v]=max( ans[i-1][v], ans[i-1][v-c[i]] + w[i] )

ans[i][v]表示从前i件物品选取放入容量为v的背包中的最大价值。对于空间复杂度进行优化时，可看到第一维每次降1，所以可以直接用一维数组保存数据ans[v]，但是注意：每次更新ans[v]时要从V向0更新。

#include<iostream>
using namespace std;
int times[101];
int worth[101];
int ans[1001];
int bag(int t, int m){
    for (int i = 0; i <= t; i++){
        ans[i] = 0;
    }
    for (int i = 0; i < m; i++){
        for (int j = t; j >= 1; j--){           // 倒序更新,不能正序
            if (j < times[i]){
                continue;
            }
            int temp = ans[j - times[i]] + worth[i];
            if (temp>ans[j]){
                ans[j] = temp;
            }
        }
    }
    return ans[t];
}
int main(){
    int t, m;
    cin >> t >> m;
    for (int i = 0; i < m; i++){
        cin >> times[i] >> worth[i];
    }
    cout << bag(t,m) << endl;
    return 0;
}

二、完全背包问题

 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

解题思路：同01背包，只是状态转移方程是：

ans[i][v]=max( ans[i][v], ans[i-1][v-c[i]] + w[i] )

ans[i][v]表示从前i件物品选取放入容量为v的背包中的最大价值。对于空间复杂度进行优化时，可看到第一维每次降1或0，所以可以直接用一维数组保存数据ans[v]，但是注意：每次更新ans[v]时要从0向V更新。除循环顺序之外，本题目与01背包完全相同。

#include<iostream>
using namespace std;
int times[101];
int worth[101];
int ans[1001];
int bag(int t, int m){
    for (int i = 0; i <= t; i++){
        ans[i] = 0;
    }
    for (int i = 0; i < m; i++){
        for (int j = 1; j<= t; j++){
            if (j < times[i]){
                continue;
            }
            int temp = ans[j - times[i]] + worth[i];
            if (temp>ans[j]){
                ans[j] = temp;
            }
        }
    }
    return ans[t];
}
int main(){
    int t, m;
    cin >> t >> m;
    for (int i = 0; i < m; i++){
        cin >> times[i] >> worth[i];
    }
    cout << bag(t,m) << endl;
    return 0;
}

三、多重背包问题

 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

解题思路： 把第i种物品换成n[i]件01背包中的物品，则得到了物品数为∑n[i]的01背包问题，直接求解，复杂度是O(V*∑n[i])。
 将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,...,2^(k-1), n[i]+1-2^{k，且k是满足n[i]+1-2}k>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。 因为， 所有整数都可以用2的幂数中的数加和得到 。
 这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为O(V*∑log n[i])的01背包问题，是很大的改进。

四、混合三种背包问题

 如果前三者混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？

解题思路：
背包与完全背包的混合：
 考虑到在P01和P02中最后给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。伪代码如下：

for i=1..N 
if 第i件物品是01背包 
for v=V..0 
f[v]=max{f[v],f[v-c[i]]+w[i]}; 
else if 第i件物品是完全背包 
for v=0..V 
f[v]=max{f[v],f[v-c[i]]+w[i]}; 

再加上多重背包 :
 如果再加上有的物品最多可以取有限次，那么如第三部分的拆分方法拆成01背包，再按照上述混合。

五、二维费用的背包问题

 二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。

解题思路：
 费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：

f [i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

 如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用顺序的循环，当物品有如完全背包问题时采用逆序的循环。当物品有如多重背包问题时拆分物品。

物品总个数的限制 :
 有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。
 另外，如果要求“恰取M件物品”，则在f[0..V][M]范围内寻找答案。

以上参考于 http://blog.csdn.net/ppp_1026hc/article/details/52138025

三、最长递增子序列LIS
寻找一个序列中的最长递增子序列的个数。