2023-08-12：用go語(yǔ)言寫(xiě)算法。實(shí)驗(yàn)室需要配制一種溶液，現(xiàn)在研究員面前有n種該物質(zhì)的
2023-08-12：用go語(yǔ)言寫(xiě)算法。實(shí)驗(yàn)室需要配制一種溶液，現(xiàn)在研究員面前有n種該物質(zhì)的溶液，
每一種有無(wú)限多瓶，第i種的溶液體積為v[i]，里面含有w[i]單位的該物質(zhì)，
研究員每次可以選擇一瓶溶液，
將其倒入另外一瓶（假設(shè)瓶子的容量無(wú)限），即可以看作將兩個(gè)瓶子內(nèi)的溶液合并，
此時(shí)合并的溶液體積和物質(zhì)含量都等于之前兩個(gè)瓶子內(nèi)的之和。
特別地，如果瓶子A與B的溶液體積相同，那么A與B合并之后，
該物質(zhì)的含量會(huì)產(chǎn)生化學(xué)反應(yīng)，使得該物質(zhì)含量增加x單位，
研究員的任務(wù)是配制溶液體積恰好等于c的，且盡量濃的溶液(即物質(zhì)含量盡量多）。
研究員想要知道物質(zhì)含量最多是多少？
對(duì)于所有數(shù)據(jù)，1 <= n, v[i], w[i], x, c <= 1000。
來(lái)自某紅書(shū)。
來(lái)自左程云。
答案2023-08-12：
大體步驟如下：
1.定義一個(gè)dp數(shù)組，長(zhǎng)度為c+1，用來(lái)存儲(chǔ)每個(gè)體積對(duì)應(yīng)的最大物質(zhì)含量。
2.初始化dp數(shù)組，將所有元素初始化為-1，表示尚未計(jì)算過(guò)。
3.對(duì)于每種溶液，如果其體積小于等于c，更新dp數(shù)組，將對(duì)應(yīng)的物質(zhì)含量設(shè)為其自身的物質(zhì)含量。
4.開(kāi)始從體積1到c的循環(huán)，對(duì)于每個(gè)體積i，在1到i/2的范圍內(nèi)循環(huán)，計(jì)算兩個(gè)瓶子合并后的物質(zhì)含量。
5.如果兩個(gè)瓶子在dp數(shù)組中有對(duì)應(yīng)的值，說(shuō)明可以進(jìn)行合并操作。
6.更新dp[i]，將其設(shè)為之前兩個(gè)瓶子內(nèi)物質(zhì)含量之和加上合并之后的額外物質(zhì)增加量。
7.返回dp[c]，即體積為c時(shí)的最大物質(zhì)含量。
時(shí)間復(fù)雜度：代碼中有兩個(gè)嵌套循環(huán)，分別遍歷n種溶液和體積范圍，因此時(shí)間復(fù)雜度為O(n*c)。
空間復(fù)雜度：使用了一個(gè)長(zhǎng)度為c+1的dp數(shù)組，因此空間復(fù)雜度為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++完整代碼如下：
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完整代碼如下：
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;
}
