关于动态规划（背包问题）讲解

Khalil

2025-07-10 19:52:57

发布于：广东

67阅读

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;
}