关于动态规划（背包问题）讲解
2025-07-10 19:52:57
发布于：广东
27阅读
0回复
0点赞
🐧企鹅PENGUIN的背包讲解
前言———————关于动态规划(DP Dynamic Programming)中的背包问题 相信有很多人都无法搞懂其中的奥义 这篇帖子的意义便是为了帮助大家理解背包问题.（看到就请点一个赞吧）
1.背包问题的特点
背包问题与贪心问题不相同 贪心问题取的答案是问题局部的最优解 而背包问题取的答案是问题整体的最优解.
贪心问题只是考虑了如何做到利益最大化 而背包问题却要多去考虑背包空间与最大利益 也就是说 贪心是在开阔平原获得更多收获 而背包是在一个划定的空间里收获更多利益 所以说 背包也就相当于贪心PLUS.
2.01背包讲解
（希望屏幕前的大家可以好好看完下列文字）
关于背包问题中的01背包问题 其主要的核心特点就是拿或不拿 试想一下 A正要与B出门爬山 A需要将一些物品放入登山包中然后带走 其物品有着I(Important 重要性) 和 W(Weight 体积)两样数据 背包也有着Z(Zone 空间）一样数据 就在此时 A要如何要如何处理才能使带的所有东西都很重要 让背包的Important值最高同时不超过背包的Zone值.
伪代码:
int total_thing,bag_zone;
cin -> t_t -> b_z;
vector<int>thing_w(t_t),thing_i(t_t),DP(b_z);
for
cin -> t_i(i) -> t_w(i);
for(int i = 1;i -> t_t;i++)
for(int j = b_z;j -> t_w(i);j--)
DP[j] = max(DP[j] or DP[j - t_w[i]] + t_i[i]);
cout <- DP[b_z];
状态转移方程：
for(int i = 1;i <= t_t;i++){
for(int j = b_z;j >= t_w(i);j--){
DP[i] = max(DP[i],DP[i - t_w[i]] + t_i[i]);
}
}
下为代码展示（有注释版和无注释版）:
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n,m;
cin >> n >> m; //输入物品数量和背包承载量
vector<int>I(n + 1),w(n + 1),dp(m + 1);//创建动态数组
for(int i = 1;i <= n;i++){
cin >> w[i] >> I[i];//输入每样物品的重量和重要性
}
for(int i = 1;i <= n;i++){//每个物品都循环背包承载量次
for(int j = m;j >= w[i];j--){
dp[j] = max(dp[j],dp[j - w[i]] + I[i]);//判断在一个承载量里的最大重要值
}
}
cout << dp[m] << "\n";//输出在背包的所有承载量中的最大重要值
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n,m;
cin >> n >> m;
vector<int>I(n + 1),w(n + 1),dp(m + 1);
for(int i = 1;i <= n;i++){
cin >> w[i] >> I[i];
}
for(int i = 1;i <= n;i++){
for(int j = m;j >= w[i];j--){
dp[j] = max(dp[j],dp[j - w[i]] + I[i]);
}
}
cout << dp[m] << "\n";
return 0;
}
3.完全背包问题讲解
完全背包实际上就是从01背包稍微改进了一下 01背包的每个物品都只可以拿一次 而完全背包可以拿多次 这就是不同之处.
伪代码:
int total_thing,bag_zone;
cin -> t_t -> b_z;
vector<int>thing_w(t_t),thing_i(t_t),DP(b_z);
for
cin -> t_i(i) -> t_w(i);
for(int i = 1;i -> b_z;i++)
for(int j = i;j -> t_t;j++)
if(i >= t_w[i])
DP[i] = max(DP[i],DP[i - t_w[i]] + t_i[i]);
cout <- DP[b_z];
状态转移方程:
for(int i = 1;i -> b_z;i++)
for(int j = i;j -> t_t;j++)
if(i >= t_w[i])
DP[i] = max(DP[i],DP[i - t_w[i]] + t_i[i]);
}
}
}
下为代码展示（有注释版和无注释版）:
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n,m;
cin >> n >> m; //输入物品数量和背包承载量
vector<int>I(n + 1),w(n + 1),dp(m + 1);
for(int i = 1;i <= n;i++){
cin >> w[i] >> I[i];//输入每样物品的重量和重要性
}
for(int i = 1;i <= m;i++){//循环背包承载量次
for(int j = 1;j <= n;j++){//每次都循环每个物品
if(i >= w[j]){//在承载量大于物品重量时才运行
dp[i] = max(dp[i],dp[i - w[j]] + I[j]);//判断在一个承载量里的最大重要值
}
}
}
cout << dp[m] << "\n";//输出在背包的所有承载量中的最大重要值
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n,m;
cin >> n >> m;
vector<int>I(n + 1),w(n + 1),dp(m + 1);
for(int i = 1;i <= n;i++){
cin >> w[i] >> I[i];
}
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(i >= w[j]){
dp[i] = max(dp[i],dp[i - w[j]] + I[j]);
}
}
}
cout << dp[m] << "\n";
return 0;
}
（看完后就请点个赞吧）
这里空空如也
有帮助，赞一个