做好闭环（四）：二分答案算法的代码统一结构

假设从链表起始点到环的起点距离为 x，那么当快慢指针中的慢指针 p 刚刚走到环的起始点位置的时候，q 指针应该在环内部距离环起始点 x 的位置上 -------------------------------------------------------------------------- 这这句话不是很严谨，距离为 x 的一半可能大于环的长度，所以这里q的位置应该是 x % L(L为环的长度)

茶艺师学编程 在我的工作环境下（Windows—DEV），输出结果为0。后来才发现问题出在get_dp函数的“return 0”上面，不管中间过程有多少状态值，经过这句通通变0。因此我改动了一下老师的代码，多重背包问题的可运行完整代码为： 最大值为37. #include <stdio.h> #define MAX_N 100 #define MAX_W 10000 int v[MAX_N + 5], w[MAX_N + 5], c[MAX_N + 5]; int v1[MAX_N + 5], w1[MAX_N + 5], n2 = 0; int dp[MAX_N + 5][MAX_W + 5]; // 添加一个0/1背包中的物品 void add_item(int v_value, int w_value) { n2++; v1[n2] = v_value; w1[n2] = w_value; return; } int get_dp(int n, int W) { int end; // 对多重背包中的每一种物品进行拆分 for (int i = 1; i <= n; i++) { // 采用二进制拆分法 for (int k = 1; k <= c[i]; c[i] -= k, k <<= 1) { add_item(k * v[i], k * w[i]); } if (c[i]) add_item(c[i] * v[i], c[i] * w[i]); } // 按照0/1背包的方式进行求解 for (int i = 1; i <= n2; i++) { for (int j = 1; j <= W; j++) { dp[i][j] = dp[i - 1][j]; if (j < w1[i]) continue; if (dp[i - 1][j - w1[i]] + v1[i] < dp[i][j]) continue; dp[i][j] = dp[i - 1][j - w1[i]] + v1[i]; end = dp[i][j]; } } printf("最大值为 %d", end); } int main(){ puts("请按顺序输入物品的价值v，重量w，数量c："); for (int i = 1; i <= 4; i++){ scanf("%d %d %d", &v[i], &w[i], &c[i]); } get_dp(4, 15); return 0; }