【动态规划问题笔记1-背包问题】最近刷题时碰到了动态规划的问题，最开始觉得很难，无从下手，研究了一下动态规划问题，觉得很神奇，做点儿笔记记录下。
结合具体的问题来理解比单独研究理论更形象一些。
问题：
要从物品重量为[2,3,5,5,10,2,8]的7个物体中选择几个物体放入容量为15的背包，恰好放满，总共有几种方案？
动态规划理论：
采用动态规划的方法来做这样的问题比较合适，动态规划采用空间换时间的策略，对于把大的问题换成小的问题，而小的问题中又相互关联的一类问题效果很好。本题中就有这样 的特征。
此处理论分析来自这里：https://www.cnblogs.com/variance/p/6909560.html
文章图片
图片中abc三个公式详细解析：
a)式表示前 ii 个物品中挑选放入承重为0的背包中和没有物品放入承重为 jj 的背包中是相等为0。
b)式表明：如果第 ii 个物品的重量大于背包的容量，则装人前 ii 个物品得到的最大价值和装入前 i?1i ? 1 个物品得到的最大价值是相同的，即物品 ii 不能装入背包。
c)式表明：如果第 ii 个物品的重量小于背包的容量，则会有一下两种情况：
(1)如果把第 ii 个物品装入背包，则背包物品的价值等于第 i?1i ? 1 个物品装入容量位 j?Wij ? W i的背包中的价值加上第 ii 个物品的价值 ViV i ;
(2)如果第 ii 个物品没有装入背包，则背包中物品价值就等于把前 i?1i ? 1 个物品装入容量为 jj 的背包中所取得的价值。
显然，取二者中价值最大的作为把前 ii 个物品装入容量为 jj 的背包中的最优解。
具体做法
生成一个7行15+1列的二维数组由于存储大动态规划的结果；其中的列代表背包重量依次为0-15,每一行代表一个物品的重量。
对于每个物体，如果物体的重量大于背包的最大容积，则该物体不能装入背包，只能使用前面的物体来装填背包；
如果物体的重量小于背包的最大容积，比较该物体放入背包和为放入背包的最大价值值，取最大的；
#include
#includeusing namespace std;
#define SUM_MAX 1000
int dp[SUM_MAX][SUM_MAX];
template
T max(const T& a, const T& b)
{
if (a > b)return a;
else return b;
}int dpCal(int n, int sum, vector& A)
{
for (int i = 0;
i j)
dp[i][j] = dp[i - 1][j];
//当物品i的重量大于背包的容量时，装不下该物品，装入之前的物品
else
//当物品i的重量小于背包的容量时，比较装入该物品时与不装入该物品时的价值大小(本题的每个物体价值可以认为是1),取最大的值。
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j] + dp[i - 1][j - A[i]]);
}
}
return dp[n-1][sum];
}int main()
{
int n, sum;
cin >> n >> sum;
if (sum > SUM_MAX)exit(1);
vector A(n, 0);
for (int i = 0;
i < n;
i++)
{
cin >> A[i];
}
int method = 0;
method = dpCal(n, sum, A);
printf("动态规划表：\n");
for (int i = 0;
i 输入:
7 15
5 5 10 2 3 4 6
输出：
文章图片
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络