小工具知识网

当前位置: 首页 > 行业知识 > 【CSP】2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝

行业知识

【CSP】2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝

2026-11-17 08:57:14 来源:互联网转载

2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/深搜+剪枝2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝

  • 2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝
    • 动态规划思路
    • 遇到的问题(补一些01背包的知识)
    • 深搜+剪枝思路
    • 动态规划完整代码
    • ���搜完整代码

      2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝

      这题由于其数据的量并不大我们可以有两种思路来解决这个问题。

      动态规划思路

      这道题其实得先想到的是动态规划,然后拼命的往上靠,或许才能想出来拐个弯。

      01背包问题都是在不超过一定容量下,求最大价值是多少,然后我们就可以将重量当作价值,就可以求出在一定容量下,求最大的占用的容量是多少。但是这个题目时求超出一定容量下最小的容量占用是多少,此时我们就可以反着想。

      题目让我们求出要选的书,我们其实也可以选出不选的书,然后剩下就是要选的书,总共的价钱减去不选的书的钱就是剩下的钱。所以这就转换成了01背包问题 容量为sum–x价值是a[i](重量)的01背包问题。

      遇到的问题(补一些01背包的知识)

      1. 首先01背包问题大家可以在网上搜到很多资源,解释的也很好,这里就简要的写一下

      01背包的状态转移方程

      f i , j = m a x ( f i , j , f i , j − w i + v i ) f_{i,j}=max(f_{i,j},f_{i,j-w_i}+v_i) fi,j​=max(fi,j​,fi,j−wi​​+vi​)

      然后针对这个题目的状态转移方程就是

      f i , j = m a x ( f i , j , f i , j − w i + w i ) f_{i,j}=max(f_{i,j},f_{i,j-w_i}+w_i) fi,j​=max(fi,j​,fi,j−wi​​+wi​)

      f i , j f_{i,j} fi,j​代表的是从前i本书中选择,在不超过容量为j的情况下,最大的容量(价值)

      1. 实现过程中遇到了一些问题

      第一个问题就是发现这个代码是错误的

      for (int i = 1; i > x;    for (int i = 1; i > a[i];        sum += a[i];    }    for (int i = 1; i = 1; j--)        {            if (j >= a[i])                dp[j] = max(dp[j], dp[j - a[i]] + a[i]);        }    }    cout > n >> x;    for (int i = 0; i > a[i];        s += a[i];    }    dfs(0, s);    cout 

上一篇:轻松搞定网关设置,一网打尽教程来袭!

下一篇:企业标准备案是啥要怎么办理