01 如何解决背包优化问题

题目：
https://www.luogu.com.cn/problem/T332242
背包空间是 10⁹ ，但内存限制是 128MB ，会超空间，那要怎么优化？

img


img

该回答引用GPT与博主@晓码自在合作编写：
这道题目的背包空间很大,直接用DP会超出内存限制。要解决这个问题,可以使用以下几种优化方法:

  1. 优化状态定义。可以不用二维数组来存储每个子问题的解,改用一维数组来优化空间复杂度。
  2. 滚动数组技巧。定一个较小的数组,循环利用这个数组来进行DP计算,以达到优化空间的目的。
  3. 分治法。可以将大范围的DP分割成几个小范围的DP进行解决,最终得到全局最优解。
  4. 离散化 + DP。通过离散化将物品重量离散化,缩小DP视窗,最后通过DP得到每个视窗的最优解,再遍历整合得到全局最优解。
    针对此题,可以使用以下策略:
  5. 一维DP数组。不用二维数组dp[i][j]表示前i个物品重量和为j的最优解。直接用一维数组dp[j]表示重量和为j的最优解。
  6. 滚动数组。设置数组长度为1000,循环利用这个数组进行DP计算。每次只考虑当前前1000个物品,通过滚动不断向后看,得到全局最优解。
  7. 离散化 + DP。将物品重量离散化,每100个物品一组,设当前视窗左右端点为L和R。通过DP得到在[L,R]范围内的最优解,然后右移视窗继续求解,最终遍历全部物品得到全局最优解。

伪代码如下:

cpp
int n, m; // 物品数量和背包重量 
vector<int> w; // 物品重量

// 一维DP数组
int[] dp;  

for (int l = 1; l <= n; l += 100) { // 离散化,每100个物品一组
    int r = min(l + 99, n); // 右端点
    for (int j = 0; j <= m; j++) dp[j] = 0; // 滚动数组,重置DP数组 
    
    for (int i = l; i <= r; i++) {
        for (int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        } 
    }
}

cout << dp[m]; // 输出最终结果

以上就是利用优化的DP策略解决这个背包问题的基本思路和实现方法。