图像灰度压缩
⼀幅4*4的图像, 灰度值序列如下.请根据课堂上所讲代码,写出构造解的S数组、l数组和b数组, 追踪解的S数组. 需要体现做题过程,如:每⼀轮i的循环写出内部j循环的前两次和最后两次, 内部循环少于等于四次的需要全部j的计算过程
Original5/28/25About 17 min
一、01 backpack problem
Given:
- Value array
v = {8, 10, 6, 3, 7, 2} - Weight array
w = {4, 6, 2, 2, 5, 1} - Knapsack capacity
c = 12
Solution analysis
1. Two-dimensional DP
m[i,j] : The largest value in the set of values with volume <=j from the first i items
Original5/14/25About 8 min
第一题
在构建 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
Original5/7/25About 6 min
4/23/25About 5 min