浅谈动态规划的背包问题即题解 P1507 【NASA的食物计划】

56 阅读 0 评论 37 点赞

我是靠谱客的博主寂寞中心，最近开发中收集的这篇文章主要介绍浅谈动态规划的背包问题即题解 P1507 【NASA的食物计划】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

借着这次机会写一写对于背包我的一些理解，也希望大佬们及时更正

一、动态规划

动态规划是求解决策过程最优化的数学方法，是指一种过程，并不算

是一类算法

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类，

本题和本题解都是关于背包问题展开的

二、背包问题

背包问题又分01背包和完全背包，二者本质区别就是可以拿物体的次

数，在这里不做区分

01背包：
有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。

求解将哪些物品装入背包可使价值总和最大。

从这个题目中可以看出，01背包的特点就是：每种物品仅有一件，可以选择放或不放。

因为动态规划的核心就是要求出状态转移方程

方法一：

这里我们先给出状态转移方程 dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])

i代表当前一共选择的物品总数量

j代表当前选择的物体总体积

dp[i-1][j]就代表我们之前i-1个物品全部选择

dp[i-1][j-c[i]]+w[i]就代表抛弃前面的不选，只选当前的这一个

而dp[i][j]就是存储当前物体的总价值

那dp[n][V]就是最终的答案，就是可以选择物体的最大重量

方法二：

看到前一个状态转移方程，大家是不是隐约有种说不上来多余的感觉？

那恭喜你，你的肝很发达

（是不是在想这跟肝有什么关系，其实我也不知道qwq（逃

那么我们还是先看状态转移方程：

dp[j]=max(dp[j],dp[j-c[i]]+w[i]

是不是爽了很多，因为[i-1]在两边都出现了，可以舍去

这就是01背包问题，是不是不算太难？那我们再来看题解

题解
第一次看题我有点小蒙，这怎么会有三个数？？？（黑人疑惑脸）

仔细想了想原来很简单，只是背包问题多了一个条件，多一重循环就好

（用方法一的就设4重循环，用方法二的就舍3重循环，但我不确定4

重会不会爆）

下面来看一看代码

#include<iostream>
using namespace std;
int mv,mm,n,v[401],m[401],k[401],dp[401][401];
int main()

没营养的前4行

注意：开数组一定要看好题目，要不然开大了爆零，开小了不过

{
cin>>mv>>mm>>n;
for(int i=1;i<=n;i++)
cin>>v[i]>>m[i]>>k[i];

没营养的5-7行

for(int i=1;i<=n;i++){
for(int j=mv;j>=v[i];j--){
for(int p=mm;p>=m[i];p--){
dp[j][p]=max(dp[j][p],dp[j-v[i]][p-m[i]]+k[i]);
}
}
}

这才是核心代码，仔细看是不是和01背包差不多呢

cout<<dp[mv][mm]; return 0; }
又是没营养的15-17行

这是我们最爱的完整代码

#include<iostream>
using namespace std;
int mv,mm,n,v[401],m[401],k[401],dp[401][401];
int main()
{
cin>>mv>>mm>>n;
for(int i=1;i<=n;i++)
cin>>v[i]>>m[i]>>k[i];
for(int i=1;i<=n;i++){
for(int j=mv;j>=v[i];j--){
for(int p=mm;p>=m[i];p--){
dp[j][p]=max(dp[j][p],dp[j-v[i]][p-m[i]]+k[i]);
}
}
}
cout<<dp[mv][mm];
return 0;
}

友情链接：
dd大神的背包九讲 https://www.cnblogs.com/jbelial/articles/2116074.html

动态规划部分来自百度 https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fr=aladdin`

百度：01背包 https://baike.baidu.com/item/01%E8%83%8C%E5%8C%85/4301245?fr=aladdin

最近一直在制作个人博客，做好了会分享做法，请大家多多支持