二进制拆分法，线性时间复杂度优化为常数时间复杂度。
是一个非常巧妙的优化方法，能够将一些复杂的问题的时间复杂度从线性级别降低到常数级别，极大地提高了算法的效率。它利用了数学上的特性和计算机硬件的并行计算能力，将问题分解成若干个独立的子问题，并通过合并结果来得到原始问题的解。
即使有多个子问题需要求解，它们的数量是有限的，可以在常数时间内完成。
另外，这些子问题是独立的，它们之间不存在依赖关系，因此可以并行地进行计算。这意味着，我们可以同时处理多个子问题，而不需要等待前一个子问题的计算结果。因此，虽然有多个子问题需要求解，但它们可以同时进行，而不是按顺序依次进行，这就是并行计算。
二进制拆分之所以被广泛应用，是因为它具有一些优势和特点：
-
简单有效：二进制拆分是一种简单而有效的拆分方法，可以将一个整数的数量（比如物品的数量）按照二进制位进行拆分，而不需要复杂的计算或规则。
-
均匀拆分：二进制拆分能够将整数均匀地拆分成若干个子问题，每个子问题的规模都相对较小。这样可以保证每个子问题的求解时间相对较短，从而提高了算法的效率。
-
容易实现：二进制拆分的实现相对简单，通常只需要进行一次循环和一些位运算即可完成。这使得二进制拆分成为一种易于理解和实现的优化方法。
-
时间复杂度降低：通过二进制拆分，将整数的数量拆分成log(k)个子问题，每个子问题的时间复杂度是常数级别的，因此整个求解过程的时间复杂度也是常数级别的，从而提高了算法的效率。
因此，尽管二进制拆分可能并不是唯一的拆分方法，但它是一种简单而有效的优化手段，能够将问题的时间复杂度从线性级别降低到常数级别，极大地提高了算法的效率。
public class DuoChongBagDp {
static class Good {
int v; // 价值
int w; // 体积/重量
public Good(int vv, int ww) {
v = vv;
w = ww;
}
}
void dp() {
int n = 10; // 物品种数
int m = 100; // 背包容量
// 二进制拆分一种物品，线性时间复杂度优化为log(k)的时间复杂度，常熟级别的 这个数值不会超过20，完成2kw到20的优化
/*
* 只有数字一次或不用，可以加法组成小于等于10正整数
* 10 = 1 + 2 + 4 + 3
* 9 = 2 + 4 + 3
* 8 = 1 + 4 + 3
* 7 = 1 + 2 + 4
* 6 = 2 + 4
* 5 = 1 + 4
* 4 = 4
* 3 = 1 + 2
* 2 = 2
* 1 = 1
*/
List<Good> goods = new ArrayList<Good>(); // 用来存储拆分完成后的物品个数 N变为远远小于N的一个数
for (int i = 0; i < n; i++) {
// 这里简单模拟下，可以不一致
int v = 3; // 价值
int w = 2; // 重量/体积
int s = 10; // 第i种物品，能够选的有效个
////二进制拆分过程，拆分s
for (int k = 1; k <= s; k *= 2) {
s -= k;
goods.add(new Good(k * v, k * w));
}
if (s > 0) {
goods.add(new Good(s * v, s * w));
}
}
int[] f = new int[m+1];
//01背包过程
for (Good good : goods) {
for (int j = m; j >= good.w; j--) {
f[j] = Math.max(f[j], f[j - good.v] + good.w);
}
}
int ans = f[m];
}
}
评论 (1)
