当前位置： 首页 > article >正文

acwing算法基础之动态规划--背包问题

article 2024/11/17 7:15:29

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

（零）
背包问题描述：有 N N N个物品，每个物品的体积是 v i v_i vi​，价值是 w i w_i wi​，现有容量是 V V V的背包，求这个背包能装下的物品的最大价值。

01背包问题：每个物品只有1个。
完全背包问题：每个物品有无穷多个。
多重背包问题：第 i i i个物品有 s i s_i si​个。
分组背包问题：有N组物品，每组有 s i s_i si​个物品，但只能选择其中一个。

（一）
01背包问题讲解。

状态定义f[i][j]：从前 i i i个物品中选择总体积不超过 j j j的物品的总价值的最大值。

状态转移：

  1. 不选择第 i i i个物品，即从前 i − 1 i-1 i−1个物品中选择总体积不超过 j j j的物品，根据状态的定义可知，为f[i-1][j]。
  2. 选择第 i i i个物品，即从前 i − 1 i-1 i−1个物品中选择总体积不超过 j − v [ i ] j-v[i] j−v[i]的物品，然后再加上w[i]，即f[i-1][j - v[i]] + w[i]。

f[i][j]的值取上述两者中的最大值即可。

初始化：f[0][0~V]=0。

最终答案：f[N][V]。

用代码表示如下，

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int v[N];
int w[N];
int f[N][N];

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 = 0; j <= m; ++j) {
            f[i][j] = f[i-1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    
    return 0;
}

考虑到上述状态转移过程中，在计算第i层的状态时，只用到了第i-1层的信息，故可以使用滚动数组进行优化，将状态表示降成一维的。可以用一个临时数组来存取上一层的状态。更进一步，考虑f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i])，发现计算f[i][j]时，需要知道f[i-1][j-v[i]]的信息，而我们可以从j=m到j=v[i]的顺序进行更新，那么使用的就是上一层的f[j-v[i]]，故省去了 O ( N ) O(N) O(N)的临时数组的空间。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int v[N];
int w[N];
int f[N];

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 = m; j >= v[i]; --j) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

（二）
完全背包问题讲解。

状态定义同上，即f[i][j]：从前 i i i个物品中选择总体积不超过 j j j的物品的总价值的最大值。

状态转移稍有不同，如下，

  1. 不选第 i i i个物品，即f[i-1][j]。
  2. 选1个第 i i i个物品，即f[i-1][j - v[i]] + w[i]。
  3. 选2个第 i i i个物品，即f[i-1][j - v[i] * 2] + w[i] * 2。
    ……
  4. 选 k k k个第 i i i个物品，即f[i-1][j - v[i] * k] + w[i] * k。

初始化：f[0][0~V]=0。

最终答案：f[N][V]。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

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 = 0; j <= m; ++j) {
            for (int k = 0; k * v[i] <= j; ++k) {
                f[i][j] = max(f[i][j], f[i-1][j - v[i] * k] + w[i] * k);
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

上述代码的三重循环可以优化到两重循环，考虑状态f[i][j]的求解，
f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] ,                                                f [ i − 1 ] [ j − v [ i ] ] + w [ i ] ,                                                           f [ i − 1 ] [ j − v [ i ] ∗ 2 ] + w [ i ] ∗ 2 ,               ⋯   ,                                                           f [ i − 1 ] [ j − v [ i ] ∗ k ] + w [ i ] ∗ k ) f[i][j] = max(f[i-1][j], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j -v[i]] + w[i], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j - v[i] * 2] + w[i] * 2,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j-v[i] * k] + w[i] * k) f[i][j]=max(f[i−1][j],                                              f[i−1][j−v[i]]+w[i],                                                         f[i−1][j−v[i]∗2]+w[i]∗2,             ⋯,                                                         f[i−1][j−v[i]∗k]+w[i]∗k)
考虑状态f[i][j - v[i]]的求解，
f [ i ] [ j − v [ i ] ] = m a x ( f [ i − 1 ] [ j − v [ i ] ] ,                                                      f [ i − 1 ] [ j − v [ i ] ∗ 2 ] + w [ i ] ,                                                            f [ i − 1 ] [ j − v [ i ] ∗ 3 ] + w [ i ] ∗ 2 ,                ⋯   ,                                                            f [ i − 1 ] [ j − v [ i ] ∗ k ] + w [ i ] ∗ k ) f[i][j - v[i]] = max(f[i-1][j- v[i]], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j -v[i] * 2] + w[i], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j - v[i] * 3] + w[i] * 2,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j-v[i] * k] + w[i] * k) f[i][j−v[i]]=max(f[i−1][j−v[i]],                                                    f[i−1][j−v[i]∗2]+w[i],                                                          f[i−1][j−v[i]∗3]+w[i]∗2,              ⋯,                                                          f[i−1][j−v[i]∗k]+w[i]∗k)
观察上式，发现有，
f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] ,                                          f [ i ] [ j − v [ i ] ] + w [ i ] ) f[i][j] = max(f[i-1][j], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i][j-v[i]] + w[i]) f[i][j]=max(f[i−1][j],                                        f[i][j−v[i]]+w[i])
故写成代码如下，

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

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 = 0; j <= m; ++j) {
            f[i][j] = f[i-1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

更进一步，可以利用滚动数组进行优化，考虑状态f[i][j]的计算公式f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i])，由于此处使用的是第i层的j-v[i]，故无需将j从j=m到j=v[i]这样倒序遍历，正序遍历即可。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

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 = 0; j <= m; ++j) {
            if (j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

（三）
多重背包问题讲解。

状态定义同（一），即f[i][j]：使用前 i i i个物体且总体积不超过 j j j，总价值的最大值。
状态转移：

  1. 不选择第 i i i个物品，即f[i-1][j]。
  2. 选择1个第 i i i个物品，即f[i-1][j-v[i]] + w[i]。
  3. 选择2个第 i i i个物品，即f[i-1][j-v[i]*2] + w[i]*2
    ……
  4. 选择s[i]个第 i i i个物品，即f[i-1][j-v[i]*s[i]] + w[i] * s[i]。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];

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 = 0; j <= m; ++j) {
            for (int k = 0; k * v[i] <= j && k <= s[i]; ++k) {
                f[i][j] = max(f[i][j], f[i-1][j - v[i] * k] + w[i] * k);
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

上述时间复杂度为 O ( n ⋅ m ⋅ s ) O(n\cdot m\cdot s) O(n⋅m⋅s)，可以优化到 O ( n ⋅ m ⋅ l o g ( s ) ) O(n\cdot m \cdot log(s)) O(n⋅m⋅log(s))。

具体介绍如下，考虑到有s[i]个第 i i i类物品，可以将其拆成 l o g ( s [ i ] ) log(s[i]) log(s[i])个，比如有20个第 i i i类物品，可以拆成1个、2个、4个、8个和5个。然后转换成01背包问题。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 25000, M = 2010;
int n, m, cnt;
int v[N], w[N];
int f[M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;//体积a，价值b，个数c
        
        int k = 1;
        while (c >= k) {
            cnt ++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            c -= k;
            k <<= 1;
        }
        
        if (c > 0) {
            cnt++;
            v[cnt] = c * a;
            w[cnt] = c * b;
        }
    }
    
    //做一遍01背包问题
    for (int i = 1; i <= cnt; ++i) {
        for (int j = m; j >= v[i]; --j) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

（四）
分组背包问题讲解。

有 N N N组物品，每组物品有 s i s_i si​类，每一类只有一个，分别有体积 v i v_i vi​、价值 w i w_i wi​，现在有体积为 V V V的背包，只能从每组物品中挑选一个或者不选，求背包的最大价值。

状态定义基本同（一），即f[i][j]：从前 i i i个物品中选择总体积不超过 j j j的，其最大价值。

状态转移，有：

  1. 不选择第 i i i组物品，f[i-1][j]。
  2. 选择第 i i i组物品中的第0个，即f[i-1][j - v[i][0]] + w[i][0]。
  3. 选择第 i i i组物品中的第1个，即f[i-1][j - v[i][1]] + w[i][1]。
    ……
  4. 选择第 i i i组物品中的第k个，即f[i-1][j - v[i][k]] + w[i][k]。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 110;
int n, m;
int s[N];
int v[N][N], w[N][N];
int f[N];

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

2 模板

暂无。。。

3 工程化

暂无。。。


http://www.kler.cn/a/147321.html

相关文章：

  • 论文笔记 SuDORMRF：EFFICIENT NETWORKS FOR UNIVERSAL AUDIO SOURCE SEPARATION
  • 每日一博 - Java的Shallow Copy和Deep Copy
  • SOLIDWORKS Toolbox：一键自动化，让紧固件与零部件管理更高效
  • 什么是Spring Boot Actuator
  • 爬虫——JSON数据处理
  • 整数唯一分解定理
  • 【服务器能干什么】搭建一个短网址平台，可以查看数据详情！
  • Java的buffer.flip()是个什么东西？
  • XML Schema中的attributeFormDefault
  • el-row el-col书写不规范的问题，会换行
  • 奖学金问题
  • Ansible的module_defaults
  • 深兰科技“汉境”入选2023年湖北省人工智能十大优秀应用案例
  • 实时云渲染简要分析
  • Python爬虫入门课: 如何实现数据抓取 ＜文字 图片 音频 视频 文档..＞
  • 通过JDBC连接MySQL实现表的插入和查看语句
  • IDEA断点调试
  • 双通道 12V 直流电机驱动芯片GC8548，12V，大电流，具有短地短电源保护功能，可替代LV8548/LV8549/ONSEMI
  • 浙江启用无人机巡山护林模式，火灾扑救效率高
  • uni-app 离线打包安卓Apk（小白上手）
  • Altium Designer学习笔记13
  • 初学Flink 学后总结
  • MYSQL基础知识之【添加数据，查询数据】
  • 微信小程序 服务端返回富文本，图片无法显示
  • java stream流的执行流程
  • 2019年9月26日: Go生态洞察：发布Go模块