动态规划是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。
目录
01背包问题
完全背包问题
多重背包问题
二维费用背包问题
（1）01背包问题
给定n个物体，和一个容量为c的背包，物品i的重量为wi，其价值为应该如何选择装入背包的物品使其获得的总价值最大。
可以用贪心算法，但是不一定能达到最优解，所以用动态规划解决
创建一个数组 dp[i][j] i为物品，j为容量，代表的值为价值
接下来要做的就是求状态转移方程
两种情况选择拿和不拿，假设w[i]为第i个的重量，c[i]为第i个的价值
推导过程如下
所以最后的状态转移方程为
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])
所以该题的解为
#include<iostream>
#include<algorithm>
using namespace std;
int dp[35][35];
int w[35], c[35];
int main() {int m, n;cin >> m >> n;for (int i = 1; i <= n; i++) {cin >> w[i] >> c[i];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (j < w[i])dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]]+ c[i]);}}cout << dp[n][m];return 0;}
也可以进行优化，因为dp的值只和上一个数据相关，所以可以循环不断更新新数据
dp[j]=max(dp[j],dp[j-w[i]]+c[i])
所以优化后完全状态的01背包代码就为（j要从后往前推，不然上一次数据可能被吞掉）
#include<iostream>
#include<algorithm>
using namespace std;
int dp[205];
int w[35], c[35];
int main() {int m, n;cin >> m >> n;for (int i = 1; i <= n; i++) {cin >> w[i] >> c[i];}for (int i = 1; i <= n; i++) {for (int j = m; j>=1; j--) {if (j > w[i])dp[j] = max(dp[j], dp[j - w[i]] + c[i]);}}cout << dp[m];return 0;}
（2）完全背包问题
直接上题
假设有种物品，每种物品有一个重量及一个价值，但每种物品的数量是无限的，同时有一个背包，最大载重量为M，从n种物品中选取若干件（每种物品可以多次放入）使其重量小于等于M，而获得的价值最大。
完全背包与01背包的区别就是完全背包的物品数量是无限的
先来个简单的方法：不断往背包中装入物品，直到背包装满
当前背包的容量j/w[i]
在01背包中加一个k循环，决定拿k个i物品，然后求价值的最大值
即for（k=0;k<i/w[i];k++) dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i])
#include<iostream>
#include<algorithm>
using namespace std;
int dp[205];
int w[35], c[35];
int main() {int m, n;cin >> m >> n;for (int i = 1; i <= n; i++) {cin >> w[i] >> c[i];}for (int i = 1; i <= n; i++) {for (int j = m; j>=1; j--) {for (int k = 0; k < i / w[i]; k++)dp[j] = max(dp[j], dp[j - k * w[i]] + k * c[i]);}}cout << dp[m];return 0;}（但是这样做时间复杂度太高了，所以我们需要再优化一下）
优化后的状态转移方程为
dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+c[i])
与01背包的区别就是从i开始而不是从i-1不需考虑上一层的状态
再将二维数组压缩成一维数组
dp[j]=max(dp[j],dp[j-w[i]]+c[i])
方程与01背包一样，但是应该从顺向推导，用到的是新数据
所以完全背包的终极写法为
#include<iostream>
#include<algorithm>
using namespace std;
int dp[205];
int w[35], c[35];
int main() {int m, n;cin >> m >> n;for (int i = 1; i <= n; i++) {cin >> w[i] >> c[i];}for (int i = 1; i <= n; i++) {for (int j = 0; j<=m; j++) {if(j>=w[i])dp[j] = max(dp[j], dp[j - w[i]] + c[i]);}}cout << dp[m];return 0;}
（3）多重背包问题
再来个小题
有n种物品和一个容量为v的背包，第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
与前两种背包的区别是每种有限件
用完全背包的思维，不断拿第i个物品个数小于等于n[i]，但是总重量小于背包容量
#include<iostream>
#include<algorithm>
using namespace std;
int dp[6100];
int w[510], v[510],s[510];
int main() {int m, n;cin >> m >> n;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>=1; j--) {for (int k = 0; k <= s[i] && j >= k * v[i]; ++k) {dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);}}}cout << dp[m];return 0;}
依旧是熟悉的配方，我们来个优化（时间复杂度太高，当s很大时根本过不了）
多重背包的二进制优化（嘿嘿，不会）
（4)二维费用背包
有N件物品和一个容量为V的背包，背包能承受的最大重量是M，每件物品只能用一次，体积是ai，重量是bi，价值是wi。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大
01背包的变种，对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值
我们设dp[i][j][k],意义为：拿到第i个物品的情况下，双重循环遍历每一个代价j和k时的最大值
所以状态转移方程式为
dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-a[i][k-b[i]]+w[i])
同样采用01背包压缩数组状态转移方程式，优化时要逆向递推
dp[j][k]=max(dp[j][k],dp[j-a[i]][k-b[i]]+w[i]);
（主包觉得这样的代码还是太吃操作了，主包决定下次再完成这个代码，觉得主包写的好的可以点点赞，觉得不好也没关系，主包还是觉得很好的，下播）
_嵌入式培训 "网线制作视频教程_h5怎么免费制作_谷歌浏览器下载安装(手机安卓版)_嵌入式培训")
