【用分治减治改造乘法与01背包问题】.pdf
94 浏览量
2023-05-13
00:05:59
上传
评论
收藏 107KB PDF 举报
用分治法改造乘法与简单背包问题用分治法改造乘法与简单背包问题
俄式乘法
大整数相乘
背包问题
01背包问题
动态规划解法
蛮力法与动态规划比较
贪心算法
俄式乘法俄式乘法
减治法减治法
若有 m * n = res，
当m为偶数时：有 m * n = (m / 2) * (n * 2)
当m为奇数时：有 m * n = (m - 1) / 2 * 2n + n
public int russian(int m,int n){
int res = 0;
while (m > 0){
if (m % 2 == 0){
m = m / 2;
n = n * 2;
}else {
res += n;
m = (m - 1) / 2;
n = 2 * n;
}
}
return res;
}
代码分析代码分析
我们可以看到，在代码中，当m为偶数时，m除以2，n乘以2；当m为奇数时，m和n会进行改变，并且把公式中多出来的
一个m加到结果res中，这样的话，就不会改变m与n直接的相乘关系，因为只有相乘关系才能满足这两个公式因为只有相乘关系才能满足这两个公式。当m除
到等于0时，m * n已经为0了，此时直接输出 res 。
大整数相乘大整数相乘
分治法分治法
资源评论
