[动态规划第一节]背包问题汇总

手机

上饶新闻上饶之窗（上饶新闻网）

内马尔身价变化：加盟巴萨时5000万欧，在巴黎最高达到1.8亿

家电

[动态规划第一节]背包问题汇总

2023-08-14 17:13:26 来源：博客园

(资料图片仅供参考)

背包问题

动态规划思路：
- 状态表示 f(i, j)
  - 状态由几维表示
    - 表示的集合是什么
      - 所有选法
      - 选法条件
        只考虑前i个物品
        总体积 <= j
    - 集合的属性是什么
      - 最大值
      - 最小值
      - 元素的数量
- 状态计算
  - 集合的划分 f(i, j)
    - 不含第i个物品
      - f(i - 1, j)
    - 包含第i个物品
      - f(i - 1, j - vi) 已知第i个物品必选，那么只要保证前i-1个物品为最大值

01背包

每件物品最多取一次

朴素代码：

const int N = 1e3 + 10;int f[N][N], v[N], w[N];int n, m;int main(){    cin >> n >> m;    for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];        //f[1~n][0] = f[0][1~m] = 0;    for(int i = 1; i <= n; ++ i) //遍历物品        for(int j = 1; j <= m; ++ j){ //遍历容量            f[i][j] = f[i - 1][j]; //不选第i个物品            if(j >= v[i])                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); //选第i个物品        }            cout << f[n][m];    return 0;}

优化：
- 用滚动数组优化
- 因为第i层总是由第i-1层来更新，不会用到1~i-2层，因此只用一维数组f[N]即可自我更新,f[j]表示不超过容量j的最大价值
- 第i个物品不取，第i层与第i-1层的总价值不变，因此可以不用更新，\(f[i][j] = f[i - 1][j]\) 这句话可删去
- 第i个物品取，因此要用i-1层更新第i层，\(f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])\) 并且总是用小容量的价值更新大容量的价值，若从小往大更新，那么小容量的价值优先被更新到第i层，大容量的价值依据小容量的价值更新时，使用的价值不再是第i-1层，所以容量要从大往小更新
- 代码：
```
const int N = 1e3 + 10;int f[N], v[N], w[N];int n, m;int main(){    cin >> n >> m;    for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];        //f[0] = 0;    for(int i = 1; i <= n; ++ i) //遍历物品        for(int j = m; j >= v[i]; -- j) //从小往大遍历容量                f[j] = max(f[j], f[j - v[i]] + w[i]); //选第i个物品            cout << f[m];    return 0;}
```

完全背包

每件物品可取无限次

朴素代码：

const int N = 1e3 + 10;int f[N][N], w[N], v[N];int n, m;int main(){    cin >> n >> m;        for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];        for(int i = 1; i <= n; ++ i) //遍历物品        for(int j = 1; j <= m; ++ j) //遍历容量            for(int k = 0; k * v[i] <= j; ++ k) //遍历个数                 f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);                    cout << f[n][m];    return 0;}

时间优化：

\(f[i][j] = max(f[i - 1][j],f[i - 1][j - v] + w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w,...,f[i-1][j-kv]+kw)\)
\(f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+w,...,f[i-1][j-kv]+(k-1)w,f[i-1][j-(k+1)v]+kw)\)
发现: \(f[i][j]=max(f[i-1][j],f[i][j-v]+w)\)

代码：

const int N = 1e3 + 10;int f[N][N], w[N], v[N];int n, m;int main(){    cin >> n >> m;        for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];        for(int i = 1; i <= n; ++ i) //遍历物品        for(int j = 1; j <= m; ++ j){ //遍历容量            f[i][j] = f[i - 1][j]; //第i个物品不选            if(j >= v[i])                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);//第i个物品选        }                    cout << f[n][m];    return 0;}

时空优化：

滚动数组优化

代码：

const int N = 1e3 + 10;int f[N], w[N], v[N];int n, m;int main(){    cin >> n >> m;        for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];        for(int i = 1; i <= n; ++ i) //遍历物品        for(int j = v[i]; j <= m; ++ j) //遍历容量            f[j] = max(f[j], f[j - v[i]] + w[i]);                    cout << f[m];    return 0;}

多重背包

每件物品可取有限次

朴素代码：

const int N = 110;int f[N][N], v[N], w[N], s[N];int n, m;int main(){    cin >> n >> m;    for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];        for(int i = 1; i <= n; ++ i)        for(int j = 1; j <= m; ++ j)            for(int k = 0; k <= s[i] && k * v[i] <= j; ++ k)                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);                    cout << f[n][m];    return 0;}

空间优化：

滚动数组优化

代码：

const int N = 110;int f[N], v[N], w[N], s[N];int n, m;int main(){    cin >> n >> m;    for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];        for(int i = 1; i <= n; ++ i)        for(int j = m; j >= v[i]; -- j)            for(int k = 0; k <= s[i] && k * v[i] <= j; ++ k)                f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);                    cout << f[m];    return 0;}

二进制优化：

将每个物品取的次数分为若干组，各组为1，2，4，8....2^k，c 的二进制数，在组中任意选取若干组，每组看作新的物品只能选一次，所有的次数都能由这几组二进制数表示，由于每组只能选一次，故化为01背包问题

代码：

const int N = 2e4 + 500;int v[N], w[N], s[N];int f[N];int n, m;int main(){    cin >> n >> m;        int cnt = 0; //记录物品个数    while(n -- ){        int V, W, S;        cin >> V >> W >> S;        int k = 1; //记录分解后每个物品的次数        while(k <= S){ //将数量S分解            cnt ++ ; //每次分解个数加一            w[cnt] = W * k;            v[cnt] = V * k;            S -= k;            k *= 2;        }        if(S > 0){ //剩余次数            cnt ++ ;            w[cnt] = W * S;            v[cnt] = V * S;        }    }        n = cnt; //01背包问题    for(int i = 1; i <= n; ++ i)        for(int j = m; j >= v[i]; -- j)            f[j] = max(f[j], f[j - v[i]] + w[i]);                cout << f[m];    return 0;}

分组背包

每个组里面最多选一件物品

朴素代码：

const int N = 110;int v[N][N], w[N][N];int f[N][N];int s[N];int n, m;int main(){    cin >> n >> m;        for(int i = 1; i <= n; ++ i){        cin >> s[i];        for(int j = 1; j <= s[i]; ++ j)            cin >> v[i][j] >> w[i][j];    }        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 <= s[i]; ++ k){ //该组选物品                if(j >= v[i][k])                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);            }        }                            cout << f[n][m];    return 0;}//或者for(int i = 1; i <= n; ++ i)for(int k = 1; k <= s[i]; ++ k)for(int j = 1; j <= m; ++ j){f[i][j] = max(f[i][j], f[i - 1][j]);if(j >= v[i][k])f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);}

空间优化：

const int N = 110;int v[N][N], w[N][N];int f[N];int s[N];int n, m;int main(){    cin >> n >> m;        for(int i = 1; i <= n; ++ i){        cin >> s[i];        for(int j = 1; j <= s[i]; ++ j)            cin >> v[i][j] >> w[i][j];    }        for(int i = 1; i <= n; ++ i)        for(int j = m; j >= 1; -- j)            for(int k = 1; k <= s[i]; ++ k)                if(j >= v[i][k])                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);                                cout << f[m];    return 0;}

关键词：

[动态规划第一节]背包问题汇总

背包问题

状态表示 f(i, j)

状态计算

01背包

完全背包

多重背包

分组背包