【蓝桥杯】背包问题--DP动态规划入门
创始人
2025-05-30 12:36:48

解题思路:

DP动态规划的思路就是:

在有 K 件物品(每个物品都有自己的重量与价值,记为w[i]、v[i])、背包容量为 W 时可以获取的最大价值,对于这种情况可以记为 f(K,W),值为可以获取的最大价值

在这种情况下有两种方式可以求解:

第一种就是:不拿第 K 件物品,在 1-(K-1)的范围内挑选物品,此时问题变为:在 K-1 件物品、背包容量为 W 时可以获取的最大价值,记为f(K-1,W);

第二种就是:拿第 K 件物品,此时背包容量为 W-(第 K 件物品所占的重量),已获取的价值为(第 n 件物品所具有的的价值),此时的问题变为在 n-1 件物品、

背包容量为 W-w[K] 时可以获取的最大价值,记为 f(K-1,W-W[K])+ V[K];

原问题的解就是两种情况中价值较大的那一个;

注意事项:

1.可以列出一个矩阵来记录所有状态下的解,val【i】【j】,i 用来枚举出 n 件物品,j 用来枚举背包容量

2.要列出状态转移方程,该题的状态转移方程为:

3.以题中例子为例:

有三个物品,背包容量为5;

参考代码:

//简单背包问题 
#include 
using namespace std;
const int maxn = 200; 
const int maxm = 5000;  //最多可以装5000重量的东西
int val[maxn+10][maxm+10];   //表示当前状态可以装的最大值,【物品个数】【背包容量】 
int w[maxn+10];  //存储物品的重量 
int v[maxn+10];  //存储物品的价值 
int main(){memset(val,0,sizeof(val));int n,m;cin>>n>>m;int ww,vv; //存储每个物品的数据    [0][i]与[i][0]都是0,一个代表可以拿0个物品,一个是还有0个剩余重量 for(int i=1;i<=n;++i){cin>>ww>>vv;w[i]=ww;v[i]=vv;}//开始处理for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(w[i]>j)   //j表示可以拿多大重量的物品val[i][j] = val[i-1][j];elseval[i][j] = max(val[i-1][j],val[i-1][j-w[i]]+v[i]); }} cout<

视频参考链接(讲的真不错)

动态规划DP0-1背包_哔哩哔哩_bilibili

相关内容

热门资讯

旅游英语欢迎词范文(推荐6篇... 旅游英语欢迎词范文 篇一Welcome Speech for International Touri...
高中英语作文:我最好的朋友 高中英语作文:我最好的朋友  高中英语作文:My Best Friend  Lucy is my b...
英语关于提醒或警告的句子【优... 英语关于提醒或警告的句子 篇一提醒和警告是我们日常生活中必不可少的一部分。它们可以帮助我们避免危险,...
英语导学案表格模板范文7篇【... 英语导学案表格模板范文7篇 篇一标题:How to Improve Your English Spe...
模范学生英语作文【经典3篇】 模范学生英语作文 篇一:积极参与校园活动As an exemplary student, activ...