一、问题重述与建模

题目描述：辰辰带着容量为T的背包上山采药，共有M株草药，每株草药有采集时间sh[i]和价值ji[i]。求在限定时间内能获得的最大价值。

数学模型：转化为0-1背包问题：

• 背包容量：总时间T

• 物品集合：M株草药

• 物品属性：重量=sh[i]，价值=ji[i]

• 目标函数：max∑ji[i]*x_i （x_i∈{0,1}）

• 约束条件：∑sh[i]*x_i ≤ T

二、动态规划算法深度分析

1. 状态定义

设dp[i][j]表示考虑前i个物品，在容量j时的最大价值。状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-sh[i]]+ji[i])  (j≥sh[i])
          dp[i-1][j]                                (j<sh[i])

2. 递推逻辑

通过二维表格逐步填充：

1. 纵向维度：物品编号1→m

2. 横向维度：背包容量0→T

3. 每个单元格依赖上方和左上方单元格

三、代码实现详解

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+100; // 双倍空间防越界
int a[maxn<<1][maxn];   // DP表格
int sh[maxn<<1],ji[maxn<<1]; // 存储输入数据

int main(){
    int t,m;
    cin>>t>>m; // 输入总时间和草药数量
    for(int i=1;i<=m;i++) 
        cin>>sh[i]>>ji[i]; // 读取每个草药耗时和价值
    
    // 动态规划核心
    for(int i=1;i<=m;i++){
        for(int j=0;j<=t;j++){
            if(j<sh[i]) 
                a[i][j]=a[i-1][j]; // 容量不足继承上一行
            else 
                a[i][j]=max(a[i-1][j-sh[i]]+ji[i],a[i-1][j]); // 状态转移
        }
    }
    cout<<a[m][t]; // 输出最终结果
    return 0;
}

关键点说明：

1. 预处理阶段：

   • 定义足够大的数组空间(maxn=1e3+100)以避免数组越界
   • 使用二维数组a存储DP状态，其中a[i][j]表示前i种草药在时间j内能获得的最大价值

2. 动态规划过程：

   • 采用双重循环结构，外层遍历草药种类(1~m)，内层遍历可用时间(0~t)
   • 状态转移分为两种情况：
     • 若当前时间不足采集草药(j < sh[i])，直接继承上一状态(a[i-1][j])
     • 否则，比较"不选当前草药(a[i-1][j])"和"选择当前草药(a[i-1][j-sh[i]] + ji[i])"的价值，取较大者

四、复杂度优化分析

1. 空间优化

传统背包问题解法使用二维数组存储状态，空间复杂度为O(mT)。通过观察状态转移方程可以发现，当前状态只依赖于前一行和更小的列值，因此可采用滚动数组技术将空间复杂度降至O(T)。具体实现如下：

int dp[maxn]; // 一维数组，maxn为最大时间容量
memset(dp, 0, sizeof(dp)); // 初始化

for(int i=1; i<=m; i++) {  // 遍历每个物品
    for(int j=T; j>=sh[i]; j--) {  // 逆序更新防止重复计算
        dp[j] = max(dp[j], dp[j-sh[i]]+ji[i]);  // 状态转移方程
    }
}

核心要点：

• 逆序更新确保每个物品只被计算一次
• 空间复杂度从O(mT)降至O(T)
• 适用于时间限制严格的大数据量场景

2. 时间优化

针对背包问题进行预处理和算法级优化：

        (1) 物品筛选预处理

vector<int> validItems;  // 存储有效物品索引
for(int i=1; i<=m; i++) {
    if(sh[i] <= T) {  // 剔除超过总时间的物品
        validItems.push_back(i);
    }
}

优化效果：

• 减少无效计算
• 预处理时间复杂度O(m)
• 后续DP过程物品数量减少

       (2) 位运算加速：

// 假设ji[i]和当前值都是正整数
for(int j=T; j>=sh[i]; j--) {
    int newVal = dp[j-sh[i]] + ji[i];
    dp[j] = (newVal > dp[j]) ? newVal : dp[j];
    // 可替换为位运算版本：
    // dp[j] ^= ((newVal > dp[j]) * (newVal ^ dp[j]));
}

适用场景：

• 对性能要求极高的嵌入式系统
• 需要微秒级优化的竞赛场景
• 大规模数据批量处理

注意事项：

• 位运算版本需要确保数值范围在安全区间
• 可能降低代码可读性
• 现代编译器通常会自动优化简单比较操作

五、正确性证明

数学归纳法：

1. 基础情况：dp[0][j]=0正确

2. 归纳假设：前i-1行计算正确

3. 归纳步骤：第i行通过max确保局部最优

最优子结构：每个状态都是前序状态的最优组合

六、变式问题探讨

1. 完全背包：每种草药无限次采集 → 正序更新

2. 多重背包：每种草药有限定次数 → 二进制拆分

3. 分组背包：草药分不同类别，每组只能选一种

4. 求方案数：修改状态定义为方案数

七、实际应用场景

1. 资源分配问题：CPU时间片调度

2. 投资组合优化：有限资金下的收益最大化

3. 广告投放策略：预算约束下的点击量优化

4. 工业排产：设备工时利用率最大化