• 周一. 4月 22nd, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

背包九讲理解(代码上的区别)

admin

11月 28, 2021
1. 01背包
问题:N种物品,每种物品1个,第i个物品重量wi,价值vi。背包容量M。选择装入背包的物品使得价值最大。
/*
二维状态:f[i][j] 表示对于前 i 个物品,总体积为 j 的情况下可以获得的最大价值。
结果:max(f[N][M])。
状态转移:
1. 不选择第 i 个物品:f[i][j] = f[i - 1][j];
2. 选择第 i 个物品:f[i][j] = f[i - 1][j - w[i]] + v[i];   注意这里状态是从第 i - 1 个物品的状态转移过来的,因为对于01背包来说如果当前要选择第 i 个物品,则代表之前一定不能选择过第 i 个物品(只能选一次)。
f[i][j] = max(1., 2.);
即:f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
初始化:f[0][0] = 0;
*/
 
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v) {
        vector<vector<int>> f(N + 1, vector<int>(M + 1));
        for(int i = 1; i <= N; i++) {
            for(int j = 0; j <= M; j++) {
                f[i][j] = f[i - 1][j];
                if(j >= w[i - 1]) f[i][j] = max(f[i][j], f[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
        int res = 0;
        for(int i = 0; i <= M; i++) res = max(res, dp[N][i]);
        return res;
    }
}
 
/*
一维状态:f[M]
状态转移:f[j] = max(f[j], f[j - w[i]] + v[i]);   这里的f[j - w[i]]是旧值,上一轮的状态。
因为到达判断第 i 个物品的状态时只与前一个物品(第 i - 1个物品)的状态有关,因此二维状态中的物品维度可以省略。但是因为原来二维状态时保留了所有前i - 1个物品选择时的状态,在计算第二个维度体积时是可以小到大计算的。但是在一维状态表示时,f[M]表示第i - 1个物品在各个体积下的状态,如果还是从小到大计算的话,第 i 个物品在某个体积下的状态将会覆盖掉第 i - 1个物品的状态,而计算f[i]的转移方程时就会出错。因为f[i][j]需要的是f[i - 1][j]和f[i - 1][j - w[i]]的状态。因此需要从大体积向小体积遍历,保证上一轮的状态没有被覆盖。
*/
 
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v) {
        vector<int> f(M + 1);
        for(int i = 1; i <= N; i++) {
            for(int j = M; j >= w[i]; j—-) {
                f[j] = max(f[j], f[j - w[i - 1]] + v[i - 1]);
            }
        }
        return f[M];
    }
}

  

2. 完全背包
问题:N种物品,每种物品无限个,第 i 个物品的体积wi,价值vi,背包容量M。选择装入背包的物品使得价值最大。
/*
朴素算法。转成01背包问题。
二维状态:f[i][j]
结果:
状态转移:
1. 不选第 i 个物品,f[i][j] = f[i - 1][j];
2. 选择 k 个第 i 个物品,f[i][j] = (f[i - 1][j - k * w[i]] + k * v[i]), 0 <= k * w[i] <= j
f[i][j] = max(1., 2.)
即:f[i][j] = max(f[i - 1][j], f[i - 1][j - k * w[i]] + v[i]);
 
一维状态:f[j]
结果:
状态转移:
*/
 
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v) {
        vector<vector<int>> f(N + 1, vector<int>(M + 1));
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                f[i][j] = f[i - 1][j];
                for(int k = 1; k * w[i - 1] <= j; k++) {
                    f[i][j] = max(f[i][j], f[i - 1][j - k * w[i - 1]] + k * v[i - 1]);
            }
        }
        int res = 0;
        for(int i = 0; i <= M; i++) res = max(res, dp[N][i]);
        return res;
    }
}
 
// 一维
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v) {
        vector<int> f(M + 1);
        for(int i = 1; i <= N; i++) {
            for(int j = M; j >= 1; j—-) {
                for(int k = 1; k * w[i - 1] <= j; k++) {
                    f[j] = max(f[j], f[j - k * w[i - 1]] + k * v[i - 1]);
            }
        }
        int res = 0;
        for(int i = 0; i <= M; i++) res = max(res, dp[N][i]);
        return res;
    }
}
 
/*
二维状态:f[i][j]表示对于前 i 个物品,体积为 j 可以获得的最大价值。
结果:f[N][M]
状态转移:
1. 不选第 i 个物品,f[i][j] = f[i - 1][j];
2. 至少选择1个第 i 个物品,f[i][j] = f[i][j - w[i]] + v[i]; 注意这里是从第 i 个物品的状态转移的,而不是而不是第 i - 1 个物品的状态转移过来,因为不知道当前选择的是第几个 i 物品,之前有个可能已经选择过第 i 个物品了。
f[i][j] = max(1., 2.)
即:f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + v[i]);
初始化:f[0][j] = 0
*/
 
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v) {
        vector<vector<int>> f(N + 1, vector<int>(M + 1));
        for(int i = 1; i <= N; i++) {
            for(int j = 1 j <= M; j++) {
                f[i][j] = f[i - 1][j];
                if(j >= w[i - 1]) f[i][j] = max(f[i][j], f[i][j - w[i - 1]] + v[i - 1]);
            }
        }
        int res = 0;
        for(int i = 0; i <= M; i++) res = max(res, dp[N][i]);
        return res;
    }
}
 
/*
一维状态:f[i]表示体积为 i 的情况下,可以获得的最大价值。
结果:res = max(f[ 0 … M]);
状态转移:f[j] = max(f[j], f[j - w[i]] + v[i]);    这里的f[j - w[i]] 是新值,当前轮的状态。
关键:与01背包问题的一维解法的区别。多维背包中f[i]是用第 i 个物品的在体积 j - w[i] 的状态更新后面在第 i 个物品的在体积 j 的状态。而01背包中f[i]是用第 i - 1个物品在体积 j - w[i] 的状态来更新在第 i 个物品的在体积 j 的状态。因为01背包每个物品只能选一次,因此如果要选择第 i 个物品,则一定是从第 i - 1个物品的状态转移过来的,而完全背包对于一个物品可以选择多次,因此需要从第 i 个物品在体积 j - w[i] 的状态转移,因为f[j - w[i]]先于f[i]计算,所以f[j - w[i]]状态可能已经包含了若干个 i 物品(具体包含了多少个 i 物品又之前的状态转移过程决定)。因此一维解法中,体积维度的遍历,01背包问题需要逆序遍历(需要的是考虑上一轮第 i - 1 个物品的更小体积的状态,逆序计算可以避免在使用之前被覆盖);而完全背包问题需要顺序遍历(需要的是考虑本轮第 i 个物品更小体积的状态,顺序计算保证使用的是更新后的状态)
*/
 
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v) {
        vector<int> f(M + 1);
        for(int i = 1; i <= N; i++) {
            for(int j = v[i]; j <= M; j++) {
                f[j] = max(f[j], f[j - w[i - 1]] + v[i - 1]);
            }
        }
        return f[M];
    }
}
3. 多重背包
问题:N种物品,第i种物品有si个,第 i 个物品的体积wi,价值vi,背包容量M。选择装入背包的物品使得价值最大。
/*
朴素算法。转为01背包问题。
一维状态:f[i]表示体积为 i 的情况下,获得的最大价值。
*/
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v, vector<int>& s) {
        vector<int> f(M + 1);
        for(int i = 1; i <= N; i++) {
            for(int j = M; j >= 1; j—-) {
                // 第 i 个物品选择 k 个
                for(int k = 0; k <= s[i - 1] && k * w[s - 1] <= j; k++) { 
                    f[j] = max(f[j], f[j - k * w[i - 1]] + k * v[i - 1]);
                }            
            }
        }
        return f[M];
    }
}
 
/*
多重背包转化为01背包问题求解。
1. 二进制拆分优化。
将原来的 si 个第 i 种物品,根据二进制拆分为ceil(log(si))种物品。得到新的物品种类。
e.g.:
第 1 种物品有 s1 = 10 个,体积 w1 = 2,价值 v1 = 3。
则可以将 10 个第 1 种物品转换成 4 种01背包的物品:
包含第1种物品的个数:1,2,4,3     // 选择其中几个可以组合出任意<=10的数,因此可以用该方法优化
体积分别是:       2,4,8,6
价值分别是:       3,6,12,9
第 2 种物品有 s2 = 3 个,体积 w2 = 1,价值 v2 = 4。
则可以将 3 个第 2 种物品转换成 2 种01背包的物品:
包含第1种物品的个数:1,2
体积分别是:       1,2
价值分别是:       4,8
*/
 
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v, vector<int>& s) {
        vector<int> new_v, new_w;
        // 二进制优化
        for(int i = 0; i < N; i++) {
            int s = s[i];
            for(int j = 1; j <= s; j <<= 1) {
                new_v.push_back(v[i] * j);
                new_w.push_back(w[i] * j);
                s -= j;
            }
            if(s) {
                new_v.push_back(v[i] * s);
                new_w.push_back(w[i] * s);
            }
        }
        N = new_v.size();
        vector<int> f(M + 1);
        for(int i = 1; i <= N; i++) {
            for(int j = M; j >= new_w[i]; j—-) {
                f[j] = max(f[j], f[j - new_w[i - 1]] + new_v[i - 1]);
            }
        }
        return f[M];
    }
}
 
/*
2. 单调队列优化。
更新状态转化为:滑动窗口内最大值。可以使用单调队列优化。
根据观察可以发现状态在跟新的时候 f 数组只和与对当前第 i 个物品的体积同余的前状态有关。可以根据该特性在每一轮状态更新时将状态 f[0 … M] 根据当前物品的体积 wi 划分为 wi 类。 
e.g.:
N, M: 2, 9
第 1 个物品w1, v1, s1: 3, 5, 2
f[9] = 5  f[6] + 5 = 5
f[9] = 10 f[3] + 10 = 10
f[8] = 5  f[5] + 5 = 5
f[8] = 10 f[2] + 10 = 10
f[7] = 5  f[4] + 5 = 5
f[7] = 10 f[1] + 10 = 10
f[6] = 5  f[1] + 5 = 5
f[6] = 10 f[0] + 10 = 10
f[5] = 5  f[2] + 5 = 5
f[4] = 5  f[1] + 5 = 5
f[3] = 5  f[0] + 5 = 5
第 2 个物品w2, v2, s2: 2, 4, 3
// 左边是新值(当前轮的状态),由右边是旧值(上一轮的状态)计算而来的
f[9] = 14  f[7] + 4 = 14    // 1 个 第2个物品
f[9] = 14  f[5] + 8 = 13    // 2 个 第2个物品
f[9] = 17  f[3] + 12 = 17   // 3 个 第2个物品
f[8] = 14  f[6] + 4 = 14    
f[8] = 14  f[4] + 8 = 13
f[8] = 14  f[2] + 12 = 12
f[7] = 10  f[5] + 4 = 9
f[7] = 13  f[3] + 8 = 13
f[7] = 13  f[1] + 12 = 12
f[6] = 10  f[4] + 4 = 9
f[6] = 10  f[2] + 8 = 8
f[6] = 12  f[0] + 12 = 12
f[5] = 9   f[3] + 4 = 9
f[5] = 9   f[1] + 8 = 8
f[4] = 5   f[2] + 4 = 4
f[4] = 8   f[0] + 8 = 8
f[3] = 5   f[1] + 4 = 4
f[2] = 4   f[0] + 4 = 4
根据对第 2 个物品体积 2 的余数分为了 2 类状态。
f[0], f[2], f[4], f[6], f[8]. 
f[1], f[3], f[5], f[7], f[9]. f[j]可以由前面不超过数量 s 的同余状态递推获得。
这相当于从前面宽度为 s 的窗口挑选最大值来更新当前状态。
转化成问题:求滑动窗口最大值?-> 单调队列维护窗口最大值!
从而可以将更新f[j]的次数缩减到1次。
因为f[j]是由前面的状态递推更新的,因此需要保存上一轮的状态。使用备份数组g。
answer = 17
*/
 
class solution {
public:
    int change(int N, int M, vector<int>& w, vector<int>& v, vector<int>& s) {
        deque<int> Q;
        vector<int> f(M + 1);
        for(int i = 1; i <= N; i++) {   // 第 i 个物品
      // f[k]是顺序更新的,旧值会被先覆盖,而在更新f[j]时用到的是旧值,因此需要备份数组保存上一轮的状态
            vector<int> g(f.begin(), f.end());  
            int w = w[i - 1], v = v[i - 1], s = s[i - 1];
            for(int j = 0; j < v; j++) {  // 按照体积 vi 将状态分为 vi 类
                for(int k = j; k <= M; k += w) {   //  对每个类使用单调队列找到窗口内最大值
                    // 判断队头元素是否还在窗口[k - s * w, k - w]内
                    if(!Q.empty() && Q.front() < k - s * w) Q.pop_front();
                    // 更新状态1.不选,2.选几个第 i 个物品的价值最大
                    if(!Q.empty()) f[k] = max(g[k], g[Q.front()] + (k - Q.front()) / w * v);
//若用g[k]比用g[Q.back()]更新f[x]能获得更大的价值,则应有:g[k] + (x - k) / w * v >= g[Q.back()] + (x - Q.back()) / w * v
                    while(!Q.empty() && g[k] >= g[Q.back()] + (k - Q.back()) / w * v)) Q.pop_back();
                    // while(!Q.empty() && g[k] - (k - j) / w * v >= g[Q.back()] + (k - Q.back()) / w * v)) Q.pop_back();
                    Q.push_back(k);
            }
        }
        return f[M];
    }
}
4. 混合背包
问题:N种物品,背包容量M。每种物品体积 wi,价值 vi。求背包可以装入物品的最大价值。
第一类物品只能用一次(01背包),第二类物品可以无限使用(完全背包),第三类物品至多只能使用 si 次(多重背包)。
/*
预处理转成两类背包问题处理:
1.01背包。
2.完全背包。
*/
 
class Solution {
private:
    struct Thing {
        int kind;
        int v, w;
    };
public:
    int change(int N, int M, vector<int>& w, vector<int>& v, vector<int>& s) {
        vector<Thing> things;
        vector<int> f(M + 1, 0);
        for(int i == 0; i < s.size(); i++) {
            if(s[i] == 0) things.push_back({0, v[i], w[i]});
            else if(s[i] == -1) things.push_back({-1, v[i], w[i]});
            else {
                int s = s[i];
                for(int k = 1; k <= s; k <<= 1) {
                    things.push_back({-1, v[i] * k, w[i] * k});
                    s -= k;
                }
                if(s > 0) things.push_back({-1, v[i] * s, w[i] * s});    
            }    
        }
        for(auto thing : things) {
            if(thing.kind < 0) {  // 01背包状态转移
                for(int j = M; j >= thing.w; j—-) 
                    f[j] = max(f[j], f[j - thing.w] + thing.v);
            }
            else {   // 完全背包状态转移
                 for(int j = thing.w; j <= M; j++) 
                    f[j] = max(f[j], f[j - thing.w] + thing.v]);
            }
        }
        return f[M];
    }
}

 

5. 二维费用背包
问题:N种物品,背包容量M,承重C。每个物品只能用一次,第 i 个物品体积wi,价值vi,重量ci。
/*
由一维01背包推广。
一维01背包状态:f[j]表示背包容量为 j 可以获得的最大价值。 结果为 f[M]。
二维01背包状态:f[j][k]表示背包容量为 j,承重为 k 可以获得的最大价值。结果为 f[M][C]。
 
类似可以推广得到二维完全背包问题,三维01背包问题…
*/
 
class solution {
public:
    int change(int N, int M, int C, vector<int>& w, vector<int>& v, vector<int>& c) {
        vector<vector<int>> f(M + 1, vector<int>(C + 1, 0));
        for(int i = 1; i <= N; i++) {
            for(int j = M; j >= w[i]; j—-) {
                for(int k = C; k >= 1; k—-) {
                    f[j][k] = max(f[j][k], f[j - w[i - 1]][k - c[i - 1]] + v[i - 1]);
                }
            }
        }
        return f[M][C];
    }
}

  

6. 分组背包
问题:N组物品,每组物品至多只能选择1个。
/*
转成01背包问题。
*/
 
7. 背包问题求方案数
8. 求背包问题的具体方案
9. 有依赖的背包问题
 
动规:
  • 状态定义
  • 状态转移
  • 结果
  • 初始化
时间:C++评测里1s差不多10^7~10^8个测试。
 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注