【干货】初始化DP的动态规划，你了解多少？

前言

就叫我沉柒吧。

动态规划

核心作用：优化

当数据范围> 30时，如果简单地使用蛮力（DFS BFS），指数枚举必须超时

另一方面，动态编程以一种巧妙的方式列举了所有的解决方案。

最后根据题目要求（属性）求解。

dp，递归，递归，搜索关系

dp 是递归，是搜索的修改版本，是递归演进。

初始化

DP的细节包括你提到的初始化问题。没有非常固定的模板。一般可以归纳为以下三种情况：

求最大值，将所有值初始化为无穷小，找到DP的起点（边界），手动赋值；

求最小值，将所有值初始化为无穷大，找到DP的起点（边界），手动赋值；

求解数，将所有值初始化为0，找到DP的起点（边界），手动赋值，一般为1。

不熟悉的时候，建议仔细找所有的边界值，给它们赋初值。这种方法绝对正确。

熟悉之后01背包问题动态规划c语言，对于一些具体的题目，可以根据经验和不影响最终答案的原则，省略部分作业步骤。

状态转移方程涉及i-1，从1开始循环到i，不涉及则从0开始。

01 背包

二维背包

有N个物品和一个容量为V的背包。每个物品只能使用一次。

第 i 项的体积为 v[i]，值为 w[i]

找出要放入背包的物品，使这些物品的总体积不超过背包容量，并且总值最大。

输出最大值。

dp[i] [j] 含义：前i项01背包问题动态规划c语言，背包容量j下的最优解（最大值）：

(1）当前状态依赖于前一个状态，可以理解为从初始状态dp[0][0] = 0开始决策，

如果有 N 个项目，则需要 N 个决策。对于第 i 个项目的每个决策，状态 f[i][j] 从前一个状态不断更新。

(2）当前背包容量不够(j < v[i])

没有选择，所以前 i 项的最优解就是前 i-1 项的最优解：

对应代码：f[i][j] = f[i - 1][j]。

(3）当前背包容量足够，可以选择，所以需要决定是否选择第i项：

选： f[i][j] = f[i - 1][j - v[i]] + w[i]。
不选：f[i][j] = f[i - 1][j] 。
我们的决策是如何取到最大价值，因此以上两种情况取 max()
我们的决策是如何取到最大价值，因此以上两种情况取 max() 

为什么选择状态转移方程 f[i] [j] = f[i – 1] [j – v[i]] + w[i]

这是我的理解

dp [i-1] [jv[i]]+w[i ] 的意思是“必须选择第i个项目”，我们怎样才能使它成为“必须选择”？

其实只要一开始就直接把第i个物品放进背包，就可以+w[i]

然后只需选择前 i-1 个项目的其余部分。

#include
using namespace std;
const int N=1e4;
int dp[N][N];// dp[i][j], j体积下前i个物品的最大价值
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n ; i ++)
    cin>>v[i]>>w[i];
    for(int i = 1; i <= n ; i ++)
        for( int j = 1 ; j <= m ; j ++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=v[i])//j            dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
        }
        cout<    return 0;
}

一维优化

因为 dp[i] 只用到了 dp[i-1] 层，那么我们只需要短时间保存上一层，然后我们就可以把这层去掉

(1)dp[j]定义：N项，背包容量j下的最优解。

(2) 注意枚举背包容量 j 必须从 m 倒序开始。

（3）为什么一维情况下枚举背包容量需要取反？

二维情况下，状态f[i][j]是从上一轮i-1的状态得到的，f[i][j]和f[i-1][j]是独立的.

优化到一维之后，如果我们还是正序，那么有f[smaller volume]更新为f[larger volume]，有可能是第i-1轮应该用，但是第i轮用了. 地位。

例如：由于 j 是从大到小循环的。假设 j = 5；j >= 2; j——；

即这一层（第i层）会先计算f[5]，

注意此时第i层正在计算f[5]，也就是说第i层没有更新f[4] f[3]，即f[4] f[3]在这次是 i – 1 层）

然后计算f[5]，需要使用比他小的f[4]或者f[3]，也就是i-1层。

(4）简单地说，在一维的情况下，正序更新状态f[j]需要之前计算的状态已经被“污染”，而逆序不存在这样的问题。

#include
using namespace std;
const int N=1e4;
int dp[N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n ; i ++)
    cin>>v[i]>>w[i];
    for(int i = 1; i <= n ; i ++)
        for( int j = m ; j >= v[i] ; j --)
        {
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
        cout<    return 0;
}

经典练习

点菜

uim 口袋里只剩下 M 元了，因为他买了一些书（M≤10000)

餐厅虽然低端，但菜品种类很多，包括N（N≤100)，

第i种卖1元（ai≤1000)因为是非常低档的餐厅，每道菜只有一份。

小A坚持“吃不完钱不放弃”的原则，所以他下单的时候一定要把所有的钱都花在uim上。

他想知道有多少种订餐方式。

dp[ j ] 表示达到当前金额时已经获得的解数；

您可以选择吃或不吃每道菜

#include
using namespace std;
const int N=1e4+10;
int dp[N];
int w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for (int i = 1 ; i <= n ; i ++)
    cin>>w[i];
    dp[0]=1;//因为当钱数==0时，说明当前方案已经成立，所以方案总数加 1
    for (int i = 1 ; i <= n ; i ++)
    for (int j = m ; j >= w[i] ; j --)
    {
  dp[j]=dp[j]+dp[j-w[i]];   
        //可以选吃喝和不吃
    } 
    cout<    return 0;
}

5x体验日

现在A已经取出x种药物，准备和那些人开始战斗。

由于每种药物只能使用一次，因此A应谨慎使用这些药物。可悲的是，如果剂量没有达到击败人所需的最低属性药量，那么人就会失败。比如他用2种药打别人，但是别人说只能用3种药打，那说明你输了，这两种属性药浪费了。

现在有n个朋友，考虑到失败的经验，胜利的经验，以及击败他所需的最低药物量。

请求求最大经验s，输出5*s。

问题解决部分：

dp[i] 代表使用 i 瓶药获得的最多经验。

1.打不过j药只能加失败经验：dp[j]=dp[j]+w1[i]

2.如果你之前打过他，你可以选择打败他获得胜利经验，也可以选择不打败他获得失败经验

然后就是0 1背包的思路：dp[j]=max(dp[j]+w1[i],dp[jv[i]]+w2[i]);

注意，如果你想打败他，你需要消耗药水，所以你需要 j – v[i]

#include
using namespace std;
const int N = 1e5+10;
long long dp[N],n,m;
long long w1[N],w2[N],v[N];
int main()
{
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++)
    cin>>w1[i]>>w2[i]>>v[i];
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = m ; j >= 0 ; j --)
        {
            if(v[i]>j)//如果 j 个迷药打不过，只能加 失败的经验
            dp[j]+=w1[i];
            else
            dp[j]=max(dp[j]+w1[i],dp[j-v[i]]+w2[i]);
            //如果打的过 ，可以选择打败他获得获胜经验，也可以选择不打败他获得失败经验。
            //这样问题就转化成了 0 1 背包问题 选和不选
        }
    } 
    cout<<5*dp[m];
    return 0;
 }

买干草

约翰损失惨重：蟑螂吃光了他所有的干草，留下一群饥饿的牛。他坐上C(1≤C≤50000)个单位的马车，去敦印家买干草。敦印有H(1≤H≤5000)捆干草) , 每个包都有它的体积 Vi (l≤Vi≤C). John 只能买整包,

他最多可以带回多少干草？

虽然这个问题是关于数量的，但可以把这个问题看作是价值和数量

这和背包问题一模一样！

#include
using namespace std;
const int N=1e5+10;
long long dp[N];
int v[N];
int main()
{
    int m,n;
    cin>>m>>n;
    for(int i = 1; i <= n ; i ++)
    cin>>v[i];
    for(int i = 1; i <= n ; i ++)
    for(int j = m; j >= v[i] ; j --)
    {
  dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
    }
    cout<    return 0;
}

完成散花

ok 以上就是动态规划01背包的全部讲解。非常感谢您在这里看到它。如果有遗漏、错误，或者更易理解的解释，欢迎私信我，我会在后面补充完善。

参考