GESP-C++六级 题库
0/1 背包(每件物品最多选一次)问题通常可用一维动态规划求解,核心代码如下。则下面说法正确的是()。
以下关于动态规划的说法中,错误的是( )。
以下关于动态规划算法特性的描述,正确的是?( )
给定 个物品和一个最大承重为 W 的背包,每个物品有一个重量 wt[i] 和价值 val[i],每个物品只能选择放或不放。
目标是选择若干个物品放入背包,使得总价值最大,且总重量不超过 W。关于下面代码,说法正确的是?( )
关于动态规划的描述,正确的是?( )
选项B正确,动态规划问题的两个必要条件:
最优子结构确保问题可分解,重叠子问题使得记忆化有意义。
以下代码实现了0/1背包问题的动态规划解法。假设物品重量为 weights[] ,价值为 values[] ,背包容量为 W ,横线上应填写?( )
以下关于动态规划的描述,( )是正确的。
动态规划要求问题具有最优子结构和无后效性。
动态规划通常通过递归来实现。
动态规划与贪心算法不同,贪心算法不适用于有重叠子问题的问题。
动态规划通常用于解决( )。(2024.9-6)
一个问题是否能用DP来解决我们的考虑一般有两点:① 最优子结构,②无后效性
最优子结构即 选项中B的可分解成相互依赖的子问题的问题,因此选B。
阅读以下用动态规划解决的0-1背包问题的函数,假设背包的容量 W 是10kg,假设输入4个物品的重量weights 分别为1,3,4,6(单位为kg),每个物品对应的价值values 分别为20,30,50,60,则函数的输出为( )。
01背包问题,dp[n][w]表示将前n个物品放入容量为w的背包中得到的最大价值,4个物品的重量为1 3 4 6,价值为20 30 50 60,背包容量为10,最大价值是1 3 6 对应的110。
在求解最优化问题时,动态规划常常涉及到两个重要性质,即最优子结构和( )。
动态规划的性质主要包括最优子结构、无后效性和有重叠子问题
最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。这意味着问题的最优解可以通过其子问题的最优解来构建。
无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。这一性质确保了动态规划方法的有效性,因为当前阶段的选择不会影响到之前阶段的状态。
有重叠子问题:子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。这一性质是动态规划算法能够通过存储和重用子问题的解来提高效率的关键。
青蛙每次能跳1或2步,下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法,错误的是( )。
状态表示:dp[i]表示青蛙到达第i个台阶的跳法。
状态转移方程:第i个台阶由两个状态转移过来①i-2级跳两步②i-1级跳一部,因此状态转移方程为:dp[i]=dp[i-1]+dp[i-2]
目标状态:dp[n]
int jump_recur(int n)使用递归方式(斐波那契),无记忆化,因此复杂度为指数。
int jump_dp(int n)使用动规(递推)方式,复杂度O(n).
以下动态规划算法的含义与目的是( )。
在求解最优化问题时,动态规划常常涉及到两个重要性质,即最优子结构和( )。
分治法
贪心策略
回溯算法
下面代码采用动态规划求解零钱兑换问题:给定 n 种硬币,第 i 种硬币的面值为 coins[i - 1] ,目标金额为 amt ,每种硬币可以重复选取,求能够凑出目标金额的最少硬币数量;如果不能凑出目标金额,返回 -1 。( )
在动态规划解决一维硬币找零问题时,若硬币面额为 [1, 3, 4] ,目标金额为 6 ,则最少需要 2 枚硬币(3+3)。( )
在解决简单背包问题时,动态规划的状态转移方程如下:
该方程表示:在考虑第 i 个物品时,当前背包容量为 w ,如果不放物品 i ,则最大价值是 dp[i-1][w] ;如果放入物品 i ,则最大价值是 dp[i-1][w - weights[i-1]] + values[i-1] ,其中数组 weights 和 values 分别表示所有物品的重量和价值,数组下标从 0 开始。
状态转移方程是动态规划的核心,可以通过递推方式表示问题状态的变化。(2024.9-6)
正确的。状态转移方程是动态规划中用来描述状态变化的重要工具。
应用动态规划算法时,识别并存储重叠子问题的解是必须的。(2024.9-6)
正确,在应用动态规划算法时,识别并存储重叠子问题的解是动态规划的核心要素之一。动态规划通过将问题分解为更小的子问题,并存储这些子问题的解,避免了重复计算相同的子问题,从而提高了算法的效率。

