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;
}
