首页 › 题库 › GESP编程能力等级认证 › 4.1 一维动态规划

GESP-C++六级 题库

共 21 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 4.1 一维动态规划 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

0/1 背包(每件物品最多选一次)问题通常可用一维动态规划求解,核心代码如下。则下面说法正确的是()。

for each item (w, v):
	for (int j = W; j >= w; --j)
		dp[j] = max(dp[j], dp[j-w] + v);
A
内层 j 必须从小到大,否则会漏解
B
内层 j 必须从大到小,否则同一件物品会被用多次
C
j 从大到小或从小到大都一样
D
只要 dp 初始为 0 ,方向无所谓
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

以下关于动态规划的说法中,错误的是( )。

A
动态规划方法通常能够列出递推公式。
B
动态规划方法的时间复杂度通常为状态的个数。
C
动态规划方法有递推和递归两种实现形式。
D
对很多问题,递推实现和递归实现动态规划方法的时间复杂度相当。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

以下关于动态规划算法特性的描述,正确的是?( )

A
子问题相互独立,不重叠
B
问题包含重叠子问题和最优子结构
C
只能从底至顶迭代求解
D
必须使用递归实现,不能使用迭代
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

给定 个物品和一个最大承重为 W 的背包,每个物品有一个重量 wt[i] 和价值 val[i],每个物品只能选择放或不放。

目标是选择若干个物品放入背包,使得总价值最大,且总重量不超过 W。关于下面代码,说法正确的是?( )

int knapsack1D(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<int> dp(W+1, 0);
    for (int i = 0; i < n; ++i) {
        for (int w = W; w >= wt[i]; --w) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}
A
该算法不能处理背包容量为 0 的情况
B
外层循环 i 遍历背包容量,内层遍历物品
C
从大到小遍历 w 是为了避免重复使用同一物品
D
这段代码计算的是最小重量而非最大价值
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

关于动态规划的描述,正确的是?( )

A
动态规划算法的时间复杂度总是低于贪心算法。
B
动态规划要求问题必须具有最优子结构和重叠子问题两个性质。
C
动态规划通过递归实现时不需要存储中间结果。
D
动态规划的核心思想是将问题分解为互不重叠的子问题。
答案与解析
正确答案:B

选项B正确,动态规划问题的两个必要条件:

最优子结构确保问题可分解,重叠子问题使得记忆化有意义。

题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

以下代码实现了0/1背包问题的动态规划解法。假设物品重量为 weights[] ,价值为 values[] ,背包容量为 W ,横线上应填写?( )

int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (weights[i-1] > j) {
                dp[i][j] = dp[i-1][j]; // 当前物品装不下
            } else {
                dp[i][j] = max(_________________________); // 在此处填入代码
            }
        }
    }
    return dp[n][W];
}
A
dp[i-1][j], values[i-1]
B
dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]
C
dp[i][j-1], values[i-1]
D
dp[i-1][j - weights[i-1]] + values[i-1], dp[i][j-1]
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

以下关于动态规划的描述,( )是正确的。

A
动态规划适用于没有重叠子问题的优化问题。
B

动态规划要求问题具有最优子结构和无后效性。

C

动态规划通常通过递归来实现。

D

动态规划与贪心算法不同,贪心算法不适用于有重叠子问题的问题。

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

动态规划通常用于解决( )。(2024.9-6)

A
无法分解的问题
B
可以分解成相互依赖的子问题的问题
C
可以通过贪心算法解决的问题
D
只能通过递归解决的问题
答案与解析
正确答案:B

一个问题是否能用DP来解决我们的考虑一般有两点:① 最优子结构,②无后效性

最优子结构即 选项中B的可分解成相互依赖的子问题的问题,因此选B。

题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

阅读以下用动态规划解决的0-1背包问题的函数,假设背包的容量 W 是10kg,假设输入4个物品的重量weights 分别为1,3,4,6(单位为kg),每个物品对应的价值values 分别为20,30,50,60,则函数的输出为( )。

#include <iostream>
#include <vector>
using namespace std;

// 0/1背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {
	vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
	
	for (int i = 1; i <= n; ++i) {
		for (int w = 0; w <= W; ++w) {
			if (weights[i - 1] <= w) {
				dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
			}
			else
			{
				dp[i][w] = dp[i - 1][w];
			}
		}
	}
	
	return dp[n][W];
}


A
90
B
100
C
110
D
140
答案与解析
正确答案:C

01背包问题,dp[n][w]表示将前n个物品放入容量为w的背包中得到的最大价值,4个物品的重量为1 3 4 6,价值为20 30 50 60,背包容量为10,最大价值是1 3 6 对应的110。

题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

在求解最优化问题时,动态规划常常涉及到两个重要性质,即最优子结构和( )。

A
重叠子问题
B
分治法
C
贪心策略
D
回溯算法
答案与解析
正确答案:A

动态规划的性质主要包括最优子结构、无后效性和有重叠子问题

最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。这意味着问题的最优解可以通过其子问题的最优解来构建。

无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。这一性质确保了动态规划方法的有效性,因为当前阶段的选择不会影响到之前阶段的状态。

有重叠子问题:子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。这一性质是动态规划算法能够通过存储和重用子问题的解来提高效率的关键。

题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

青蛙每次能跳1或2步,下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法,错误的是( )。

int jump_recur(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	return jump_recur(n - 1) + jump_recur(n - 2);
}

int jump_dp(int n) {
	vector<int> dp(n + 1); // 创建一个动态规划数组,用于保存已计算的值
	// 初始化前两个数
	dp[1] = 1;
	dp[2] = 2;
	// 从第三个数开始计算斐波那契数列
	for (int i = 3; i <= n; ++i) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}


A
函数jump_recur()采用递归方式。
B
函数jump_dp()采用动态规划方法。
C
当n较大时,函数jump_recur()存在大量重复计算,执行效率低。
D
函数jump_recur()代码量小,执行效率高。
答案与解析
正确答案:D

状态表示: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).

题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

以下动态规划算法的含义与目的是(   )。

int function(vector<int>& nums) {
	int n = nums.size();
	if (n == 0)
		return 0;
	if (n == 1)
		return nums[0];
	vector<int> dp(n, 0);
	dp[0] = nums[0];
	dp[1] = max(nums[0], nums[1]);
	for (int i = 2; i < n; ++i) {
		dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
	}
	return dp[n - 1];
}
A
计算数组 nums 中的所有元素的和
B
计算数组 nums 中相邻元素的最大和
C
计算数组 nums 中不相邻元素的最大和
D
计算数组 nums 中的最小元素
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

在求解最优化问题时,动态规划常常涉及到两个重要性质,即最优子结构和(   )。

A
重叠子问题
B

分治法

C

贪心策略

D

回溯算法

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
14 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

下面代码实现了动态规划版本的斐波那契数列计算,其时间复杂度是 。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
15 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

下面代码采用动态规划求解零钱兑换问题:给定 n 种硬币,第 i 种硬币的面值为 coins[i - 1] ,目标金额为 amt ,每种硬币可以重复选取,求能够凑出目标金额的最少硬币数量;如果不能凑出目标金额,返回 -1 。( )

int coinChangeDPComp(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    vector<int> dp(amt + 1, MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a)
                dp[a] = dp[a];
            else
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
16 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

在动态规划解决一维硬币找零问题时,若硬币面额为 [1, 3, 4] ,目标金额为 6 ,则最少需要 2 枚硬币(3+3)。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

在解决简单背包问题时,动态规划的状态转移方程如下:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);

该方程表示:在考虑第 i 个物品时,当前背包容量为 w ,如果不放物品 i ,则最大价值是 dp[i-1][w] ;如果放入物品 i ,则最大价值是 dp[i-1][w - weights[i-1]] + values[i-1] ,其中数组 weights 和 values 分别表示所有物品的重量和价值,数组下标从 0 开始。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

状态转移方程是动态规划的核心,可以通过递推方式表示问题状态的变化。(2024.9-6)

A
对
B
错
答案与解析
正确答案:对

正确的。状态转移方程是动态规划中用来描述状态变化的重要工具。

题目详情
19 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

应用动态规划算法时,识别并存储重叠子问题的解是必须的。(2024.9-6)

A
对
B
错
答案与解析
正确答案:对

正确,在应用动态规划算法时,识别并存储重叠子问题的解是动态规划的核心要素之一。动态规划通过将问题分解为更小的子问题,并存储这些子问题的解,避免了重复计算相同的子问题,从而提高了算法的效率。

题目详情
20 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

在动态规划中,状态转移方程的作用是定义状态之间的关系。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情