牛客DP41精讲：当背包必须装满时，你的状态转移方程该如何调整？

题目重解

我们面对一个经典背包问题的变体：给定n个物品，每个物品有重量w和价值v，背包容量为V。需要回答两个问题：1) 普通情况下能获得的最大价值；2) 必须恰好装满背包时的最大价值（若无法装满则输出0）。这就像旅行前收拾行李箱，既要考虑普通装箱，又要应对航空公司严格的重量限制。

解题思路

代码分为清晰的两阶段：

常规背包处理：初始化dp数组全为0，通过逆序更新保证物品只选一次。状态转移方程dp[j] = max(不选当前物品, 选当前物品)体现经典01背包思想。

必须装满的处理：将dp初始值设为负数（代码中用-10000模拟），仅dp[0]=0。这样只有恰好达到j容量的状态才能被有效转移，最终结果需与0比较避免负值输出。

代码和注释

#include <cstdlib>
#include<iostream>
using namespace std;
int main() {
    // 输入物品数n和背包容量V
    int n, V;
    cin >> n >> V;

    // 动态分配数组存储重量w和价值v
    int* v=new int[n];
    int* w=new int[n];
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];

    // 常规01背包处理
    int* dp = new int [V + 1]; 
    for(int i=0;i<=V;i++){
        dp[i]=0; // 初始化：什么都不装时价值为0
    }

    for(int i=1;i<=n;i++){ // 遍历每个物品
        for(int j=V;j>=w[i-1];j--){ // 逆序更新防止重复选取
            dp[j]=max(dp[j], v[i-1]+dp[j-w[i-1]]); // 经典状态转移
        }
    }
    cout<<dp[V]<<endl; // 输出常规解

    // 必须装满背包的处理
    for(int i=1;i<=V;i++){
        dp[i]=-10000; // -∞初始化表示不可达状态
    }

    for(int i=1;i<=n;i++){
        for(int j=V;j>=w[i-1];j--){
            dp[j]=max(dp[j], v[i-1]+dp[j-w[i-1]]); // 转移方程相同但初始条件不同
        }
    }
    cout<<max(dp[V],0); // 负数时输出0表示无法装满
    return 0;
}