思路

将这道题分为两个部分。

第一部分

给你

n

类物品。每种价值

V_i

，体积为

W_i

，数量为

D_i

，背包体积为

C

的最大价值。

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

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

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

也可自行理解。

代码

CPP

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

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

代码

CPP

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$ 个开始枚举。

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

题解：P1782 旅行商的背包

文章操作

思路

第一部分

代码

第二部分

代码

相关推荐

评论

题解：P1782 旅行商的背包