Sam的背包问题

Blog
题目传送门
题意很简单，就不再赘述了。
题目已经很明显地提醒了背包，哪十有八九就是 $dp$ 了。

朴素背包：
$dp_{i,j,k}$ 表示考虑了前 $i$ 个物品，总重量不超过 $j$，总体积不超过 $k$ 时的最大收益。
转移：

1. 第 $i$ 个物品不选，即 $dp_{i-1,j,k}$;
2. 第 $i$ 个物品不选，即 $dp_{i-1,j-h_i,w-v_i}+w_i$.

综上，$dp_{i,j,k}=max\{dp_{i-1,j,k}, dp_{i-1,j-h_i,k-v_i}+w_i\}$.

那么，我们可以枚举 $x$，将所有的情况取 max 即可。

你会发现空间炸了，那么只要将 $j, k$ 倒叙枚举即可，此时 $dp_{j-h_i,k-v_i}$ 一定没有更新。

$ans = \max_{x=0}^H dp_{H-x,V+x}$

题解

设选中物品的总重量为 $h$，总体积为$(v$。

神奇背包需要存在一个自然数 $x$，满足：

$$h\le H-x,\quad v\le V+x$$

化简：

$$x\le H-h$$ $$x\ge v-V$$

又因为 $x\ge0$，所以：

$$\max(0,v-V)\le H-h$$

等价于：

$$\boxed{h\le H,\quad h+v\le H+V}$$

因此问题变成：

选择若干物品，使：

• 总重量不超过 (H)
• 总重量 + 总体积不超过 (H+V)

价值最大。

---

DP

定义：

$$dp[i][j]$$

表示当前总重量为 (i)，总体积为 (j) 时的最大价值。

转移：

$$dp[i][j]=\max(dp[i][j],dp[i-h][j-v]+w)$$

因为物品只能选一次，所以两个维度倒序枚举。

初始化：

dp[0][0]=0

其余为负无穷

最后枚举所有：

$$i\le H,\ i+j\le H+V$$

取最大值。

---

复杂度

状态数：

$$O(H(H+V))$$

转移：

$$O(nH(H+V))$$

假设 Sam 选择了一组物品集合 $S$，其总重量为 $A = \sum_{i \in S} h_i$，总体积为 $B = \sum_{i \in S} v_i$。

根据题意，需要存在一个自然数 $x \ge 0$，使得选择的物品满足：

• $A \le H - x \implies x \le H - A$
• $B \le V + x \implies x \ge B - V$

因此，只需能够找到一个非负整数 $x$ 满足 $\max(0, B - V) \le x \le H - A$。此类非负整数 $x$ 存在的充要条件为：

• $H - A \ge 0 \implies A \le H$
• $H - A \ge B - V \implies A + B \le H + V$

问题化简为：选择若干物品，在满足总重量 $A \le H$ 且 总重量与总体积之和 $A + B \le H + V$ 的前提下，求解能获得的最大价值和。

这是一个标准的二维 01 背包问题：

• 第一维度限制：总重量 $j \le H$（最大为 $300$）。
• 第二维度限制：总重量 + 总体积 $k \le H + V$（最大为 $600$）。

定义 f[j][k] 表示总重量不超过 $j$ 且（总重量+总体积）不超过 $k$ 时的最大价值。

对于每个物品 $i$（重量 $h_i$，体积 $v_i$，价值 $w_i$），令 $sum_i = h_i + v_i$：

$$f[j][k] = \max(f[j][k], f[j - h_i][k - sum_i] + w_i)$$

采用倒序遍历实现滚动数组，时间复杂度为 $O(n \cdot H \cdot (H + V))$，运算量约为 $1000 \times 300 \times 600 = 1.8 \times 10^8$。

以下大家的思路已经十分清晰了
再此补一份代码：

#include<bits/stdc++.h>
#define ll long long//不开long long见祖宗
using namespace std;

const int N=1e3+5;//605 1e3+5省事

int n,H,V;
ll dp[N][N];

int main(){
    freopen("dp.in","r",stdin);
    freopen("dp.out","w",stdout);

    cin>>n>>H>>V;
    for(int i=1;i<=n;i++){
        int h,v;ll w;cin>>h>>v>>w;
        for(int j=H;j>=h;j--){//∑h_i<=j H-x<=H
            for(int k=V+H;k>=v;k--){//∑v_i<=k V+x<=V+H
                dp[j][k]=max(dp[j][k],dp[j-h][k-v]+w);
                //不选i，dp[j][k]在滚动数组中为以前的答案
                //选i，在以前质量没有h，体积没有v的时候的答案加上i的价值
            }
        }
    }

    ll ans=0;
    for(int i=0;i<=H;i++)//枚举每个x
        ans=max(ans,dp[H-i][V+i]);

    cout<<ans<<'\n';
}

定义 $f_{i,j,k}$ 为前 $i$ 个物品， $\sum h_i\le j$ 且 $\sum v_i\le k$ 的最大价值。则 $f_{i,j,k}=\max\{f_{i-1,j,k},f_{i-1,j-h_i,k-v_i}+w_i\}$ ，然后滚动数组就行。

直接 DP 得出 $h \le i \ \&\& \ w \le j$ 的方案数，得出结论：显然得出答案，直接秒杀。

$ans = dp[a][b], a + b = h + w$ 且 $0 \le a \le h$