2023-08-12：用 go 语言写算法。实验室需要配制一种溶液，现在研究员面前有 n 种该物质的溶液，
每一种有无限多瓶，第 i 种的溶液体积为 v[i]，里面含有 w[i]单位的该物质，
研究员每次可以选择一瓶溶液，
将其倒入另外一瓶（假设瓶子的容量无限），即可以看作将两个瓶子内的溶液合并，
此时合并的溶液体积和物质含量都等于之前两个瓶子内的之和。
特别地，如果瓶子 A 与 B 的溶液体积相同，那么 A 与 B 合并之后，
该物质的含量会产生化学反应，使得该物质含量增加 x 单位，
研究员的任务是配制溶液体积恰好等于 c 的，且尽量浓的溶液(即物质含量尽量多）。
研究员想要知道物质含量最多是多少？
对于所有数据，1 <= n, v[i], w[i], x, c <= 1000。
来自某红书。
来自左程云。
答案 2023-08-12：
大体步骤如下：
1.定义一个 dp 数组，长度为 c+1，用来存储每个体积对应的最大物质含量。
2.初始化 dp 数组，将所有元素初始化为-1，表示尚未计算过。
3.对于每种溶液，如果其体积小于等于 c，更新 dp 数组，将对应的物质含量设为其自身的物质含量。
4.开始从体积 1 到 c 的循环，对于每个体积 i，在 1 到 i/2 的范围内循环，计算两个瓶子合并后的物质含量。
5.如果两个瓶子在 dp 数组中有对应的值，说明可以进行合并操作。
6.更新 dp[i]，将其设为之前两个瓶子内物质含量之和加上合并之后的额外物质增加量。
7.返回 dp[c]，即体积为 c 时的最大物质含量。
时间复杂度：代码中有两个嵌套循环，分别遍历 n 种溶液和体积范围，因此时间复杂度为 O(n*c)。
空间复杂度：使用了一个长度为 c+1 的 dp 数组，因此空间复杂度为 O(c+1)，即 O(c)。
go 完整代码如下：
package main
import ( "fmt" "math")
func maxValue(v []int, w []int, x int, c int) int { n := len(v) dp := make([]int, c+1) for i := range dp { dp[i] = -1 } for i := 0; i < n; i++ { if v[i] <= c { dp[v[i]] = int(math.Max(float64(dp[v[i]]), float64(w[i]))) } } for i := 1; i <= c; i++ { for j := 1; j <= i/2; j++ { if dp[j] != -1 && dp[i-j] != -1 { dp[i] = int(math.Max(float64(dp[i]), float64(dp[j]+dp[i-j]+bonus(x, j, i-j)))) } } } return dp[c]}
func bonus(x, j, k int) int { if j == k { return x } return 0}
func main() { v := []int{5, 3, 4} w := []int{2, 4, 1} x := 4 c := 16 fmt.Println(maxValue(v, w, x, c))}
复制代码
rust 完整代码如下：
fn max_value(v: &[i32], w: &[i32], x: i32, c: i32) -> i32 { let n = v.len(); let mut dp = vec![-1; (c + 1) as usize];
for i in 0..n { if v[i] <= c { dp[v[i] as usize] = dp[v[i] as usize].max(w[i]); } }
for i in 1..=c { for j in 1..=(i / 2) { if dp[j as usize] != -1 && dp[(i - j) as usize] != -1 { let val = dp[j as usize] + dp[(i - j) as usize] + if j == (i - j) { x } else { 0 }; dp[i as usize] = dp[i as usize].max(val); } } }
dp[c as usize]}
fn main() { let v = vec![5, 3, 4]; let w = vec![2, 4, 1]; let x = 4; let c = 16;
println!("{}", max_value(&v, &w, x, c));}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <algorithm>
int maxValue(std::vector<int>& v, std::vector<int>& w, int x, int c) { int n = v.size(); std::vector<int> dp(c + 1, -1); // dp[i] = -1, no solution to obtain volume i so far
// Set values for naturally available volumes for (int i = 0; i < n; i++) { if (v[i] <= c) { dp[v[i]] = std::max(dp[v[i]], w[i]); } }
for (int i = 1; i <= c; i++) { for (int j = 1; j <= i / 2; j++) { if (dp[j] != -1 && dp[i - j] != -1) { int val = dp[j] + dp[i - j] + (j == i - j ? x : 0); dp[i] = std::max(dp[i], val); } } }
return dp[c];}
int main() { std::vector<int> v = { 5, 3, 4 }; std::vector<int> w = { 2, 4, 1 }; int x = 4; int c = 16;
std::cout << maxValue(v, w, x, c) << std::endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>
int maxValue(int* v, int* w, int x, int n, int c) { int* dp = (int*)malloc((c + 1) * sizeof(int));
for (int i = 0; i <= c; i++) { dp[i] = -1; }
for (int i = 0; i < n; i++) { if (v[i] <= c) { *(dp + v[i]) = (*(dp + v[i]) > w[i]) ? *(dp + v[i]) : w[i]; } }
for (int i = 1; i <= c; i++) { for (int j = 1; j <= i / 2; j++) { if (*(dp + j) != -1 && *(dp + i - j) != -1) { *(dp + i) = (*(dp + i) > ((*(dp + j)) + (*(dp + i - j)) + (j == i - j ? x : 0))) ? *(dp + i) : ((*(dp + j)) + (*(dp + i - j)) + (j == i - j ? x : 0)); } } }
int result = *(dp + c); free(dp); return result;}
int main() { int v[] = { 5, 3, 4 }; int w[] = { 2, 4, 1 }; int x = 4; int c = 16; int n = sizeof(v) / sizeof(v[0]); printf("%d\n", maxValue(v, w, x, n, c));
return 0;}
复制代码
![2023-08-12：用go语言写算法。实验室需要配制一种溶液，现在研究员面前有n种该物质的溶液， 每一种有无限多瓶，第i种的溶液体积为v[i]，里面含有w[i]单位的该物质， 研究员每次可以选择一瓶_左程云_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论