题解：P1782 旅行商的背包

lflby · 2025-07-28 16:08:03 · 题解

思路

将这道题分为两个部分。

第一部分

给你 n 类物品。每种价值 V_i，体积为 W_i，数量为 D_i，背包体积为 C 的最大价值。

注意：题目中价值为 W_i，体积为 V_i。

一眼多重背包，在一眼时间复杂度不难想到二进制优化。

不会二进制优化的可以先去做 宝物筛选。

也可自行理解。

代码

for (int i = 1; i <= n; i++)
{
  int W=read(),V=read(),D=read();
  for (int j = 1; j <= D; j*=2)
  {
    v[++cnt]=V*j;
    w[cnt]=W*j;
    D-=j;
  }
  if (D)
  {
    v[++cnt]=V*D;
    w[cnt]=W*D;
  }
}
for (int i = 1; i <= cnt; i++)
{
  for (int j = C; j >= w[i]; j--)
  {
    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  }
}

第二部分

看到 m \le 5 不难想到可以直接枚举。

对于每个物品运用前面的 dp 继续计算。

注意 dp 的无后效性，所以要从后往前，先枚举大小再枚举个数。

代码

for (int i = 1; i <= m; i++)
{
  int a=read(),b=read(),c=read();
  for (int x = C; x >= 0; x--)
  {
    int y = a*x*x+b*x+c;
    for (int j = C; j >= x; j--)
    {
      dp[j]=max(dp[j],dp[j-x]+y);
    }
  }
}

注意：每个物品从 0 个开始枚举。

关键代码已给出，其余代码自行补充。