图像灰度压缩
⼀幅4*4的图像, 灰度值序列如下.请根据课堂上所讲代码,写出构造解的S数组、l数组和b数组, 追踪解的S数组. 需要体现做题过程,如:每⼀轮i的循环写出内部j循环的前两次和最后两次, 内部循环少于等于四次的需要全部j的计算过程
构造阶段的b数组
原创5/28/25大约 17 分钟
一、01背包问题
给定：
- 价值数组
v = {8, 10, 6, 3, 7, 2} - 重量数组
w = {4, 6, 2, 2, 5, 1} - 背包容量
c = 12
解决方案分析
1. 二维动态规划
定义 m[i,j]：从前 i 个物品中选择，总体积不超过 j 的最大价值。
- 如果
j < w[i-1]：m[i,j] = m[i-1,j]（不能选择第i个物品） - 否则：
m[i,j] = max(m[i-1,j], m[i-1,j-w[i-1]] + v[i-1])（选择或不选择第i个物品）
原创5/14/25大约 6 分钟
第一题
在构建 c 数组时，不再维护额外的 b 数组来记录方向。 在需要回溯寻找具体的最长公共子序列时，直接通过比较 c[i] [j]、c[i-1] [j] 和 c[i] [j-1] 的值来判断当前字符是否属于最长公共子序列，以及应该向哪个方向回溯。
伪代码
FUNCTION LCS(const string s1, const string s2):
m = s1.size() // 获取字符串 s1 的长度
n = s2.size() // 获取字符串 s2 的长度
dp[m+1][n+1] // 初始化动态规划表
for i from 1 to m:
for j from 1 to n:
if s1[i-1] == s2[j-1]: // 如果当前字符相同
dp[i][j] = dp[i-1][j-1] + 1 // 当前位置的 LCS 长度等于左上方的值加 1，表示找到了一个公共子序列字符
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // 如果当前字符不同，当前位置的 LCS 长度取上方和左方的最大值，表示不考虑当前字符
end for
end for
return dp[m][n] // 返回最终的最长公共子序列长度，位于动态规划表的右下角
END FUNCTION
原创5/7/25大约 6 分钟
4/23/25大约 5 分钟