一、背包

01背包
完全背包
多重背包

分组背包

01背包问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
思路：
二维数组的方式比较简单不再写了，重点记录下一维数组的dp。一维数组的递推式为dp[j]=max(dp[j],dp[j-w[i]]+v[i])。意思就是在第i次循环时，也就是在考虑是否选取第i个物品的时候，利用之前记录的0-W大小的背包来更新当前情况下j容量的数据。值得注意的是循环的顺序与完全背包正好相反，试想如果我们从0循环到W，那么我们会发现前面如果更新了一次值，在后面的计算中我们就会使用之前更新的值，也就是说我们选了同一个物品2次。这跟01背包每个物品选一次是相悖的。而从W循环到0就没有这种问题了。
代码:

#include <iostream>
#include <cstring>
#include <string>

using namespace std;
int main(){
    int n,mw,v[1000],w[1000],dp[1000];
    while(cin>>n>>mw){
        for(int i=0;i<n;i++)cin>>v[i]>>w[i];
            for(int i=0;i<n;i++){ for(int j=mw;j<=w[i];j--){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        cout<<dp[mw]<<endl;
    }
    return 0;
}

关于初始化

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。
HDU - 2602 Bone Collector
思路：
模板题
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>

using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {   
    int n, v, val[1005], vol[1005], dp[1005] = { 0 };
    cin >> n >> v;
    for (int i = 0;i < n;i++)cin >> val[i]; 
        for (int i = 0;i < n;i++)cin >> vol[i];
            for (int i = 0;i < n;i++) { for (int j = v;j >= vol[i];j--) {
                dp[j] = max(dp[j], dp[j - vol[i]] + val[i]);
            }
        }
        cout << dp[v] << endl;
    }
    return 0;
}
完全背包问题
思路：
为了解决这个问题，我们通常的想法是修改递推式为dp[i][j]=max(dp[i][j],dp[i][j-kw[i]]+kv[i])但是如果使用这个递推式那么程序中就会有一个三重循环，时间复杂度非常的糟糕。为了减少时间复杂度，我们就要用到之前01背包中使用的对于一维数组操作。01中我们从W到0，在这里我们使用0-W就可以从小到大一个不漏的更新。
FATE HDU - 2159
思路:
二维完全背包的题目，限制条件为忍耐度和最多杀怪的数量。递推关系是dp[j][k]=max(dp[j][k],dp[j-end[i]][k—]+exp[i])
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstring>

using namespace std;
int main() {
    int n, m, k, s, end[100], exp[100],dp[105][105];
    while (cin >> n >> m >> k >> s) {
        int i,j,l,min=999999999;
        memset(dp, 0, sizeof(dp));
        for (i = 0;i < k;i++) { cin >> exp[i] >> end[i];}
        for (i = 0;i < k;i++) {
            for (j = end[i];j <= m;j++) {
                for (l = 1;l <= s;l++) { dp[j][l] = max(dp[j][l], dp[j - end[i]][l - 1] + exp[i]); if (dp[j][l] >= n&&j < min)min = j;
                }
            }
        }
        if (min <= m)cout << m-min << endl;
        else cout << -1 << endl;
    }
    return 0;
}
二、LIS
Super Jumping! Jumping! Jumping! HDU - 1087
思路:
把LIS模板中的长度换成和
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstring>

using namespace std;
int main() {
    int n,a[1005],dp[1005];
    while (cin >> n&&n) {
    int res = 0;
    for (int i = 0;i < n;i++) cin >> a[i];
    for (int i = 0;i < n;i++) {
        dp[i] = a[i];
        for (int j = 0;j < i;j++) {
            if (a[j] < a[i])dp[i] = max(dp[i], dp[j] + a[i]); } if (dp[i] > res)res = dp[i];
        }
        cout << res<< "\n";
    }
    return 0;
}