本题是一个变形的背包问题:每个样本可以选择两种“花费”(试剂),其中一种会额外消耗 1 张快速分析卡。目标是先最大化完成样本数,在此基础上最小化试剂总消耗,并满足试剂 ≤ R、快速分析卡 ≤ T。
算法:动态规划(DP,二元约束下的最优化-可行性分离)
dp[j][k] 表示在处理若干样本后,恰好完成 j 个样本、使用 k 张快速分析卡时的最小试剂总消耗。
初始化:dp[0][0] = 0,其余为正无穷。某生物研究中心有 N 个待处理的样本,每个样本可以选择两种分析方法:标准分析和快速分析。标准分析会消耗一定量的试剂,快速分析虽然消耗的试剂较少,但每次使用需要消耗一张快速分析卡。研究室目前储备有 R 单位试剂和 T 张快速分析卡。现在需要规划样本的分析方案,目标是在保证完成尽可能多样本的前提下,使得试剂的总消耗量最少。请你计算最多能完成多少个样本,以及在此情况下试剂的最小总消耗。
约束:样本数量 N 不超过 100,试剂总量 R 不超过 5000,快速分析卡数量 T 不超过 50,每个样本在两种分析方式下的试剂消耗均为 1 到 50 之间的整数。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册