92、新一的宝藏搜寻.docx

解题思路

思路

这是一个典型的背包问题，但有一些独特的地方。在传统的背包问题中，每种物品只有一件。然而，在这个问题中，每种宝物的数量可以多于一件。这个问题可以转化为一个多重背包问题。

在这个问题中，我们的目标是选择一些宝物，使得它们的总体积不超过背包的容量，同时使得这些宝物的总价值最大。为了达到这个目标，我们可以使用动态规划（DP）的方法。

动态规划的主要思想是将复杂问题分解为若干个简单子问题，并存储子问题的解，以避免重复计算。对于这个问题，我们可以定义一个DP数组?f，其中?f[j]?表示背包容量为?j?时的最大价值。

但是，如果我们直接处理多重背包问题，时间复杂度会达到?O(N×V×S)，其中N?是宝物种类数，V?是背包容量，S?是宝物的最大数量。这样的时间复杂度对于这个问题来说太高了。

因此，我们需要引入二进制优化，将多重背包问题转化为0-1背包问题，从而将时间复杂度降低到?O(N×V×∑logSi)。

解题步骤：

步骤一：二进制优化

为了把多重背包问题转化为0-1背包问题，我们可以使用二进制优化。二进制优化的基本思想是利用二进制数的性质，把每种宝物分解为若干个单独的物品，每个物品只有一件。

具体来说，假设第i种宝物有?s_isi?件，我们可以将这种宝物分解为若干个宝物，每个宝物的数量为二进制数的幂（即1，2，4，8，...）。注意，如果?si?不是二的幂，那么最后还会剩下一些宝物，数量为?si?减去最大的二的幂。

例如，如果si=10，我们可以将它分解为1+2+4=7和3两个部分。这样，我们就把一个多重背包问题转化为一个0-1背包问题。

步骤二：动态规划

转化为0-1背包问题后，我们可以使用动态规划的方法来求解。我们遍历所有的宝物（包括分解后的宝物），对于每个宝物，我们遍历所有的背包容量?j，如果?j?大于或等于宝物的体积?v[i]，那么我们就可以选择是否拿这件宝物。如果拿了，背包的容量就会减少?v[i]，价值会增加w[i]。

状态转移方程为：f[j]=max(f[j],f[j?v[i]]+w[i])。

步骤三：输出最大价值

遍历完所有的宝物后，f[m]?就是背包的最大价值，其中?m?是背包的容量。

总的来说，这个问题的解题步骤是：

使用二进制优化，把每种宝物分解为若干个单独的物品，每个物品只有一件。

使用动态规划，遍历所有的物品和所有的背包容量，更新DP数组。

输出最大价值。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

constintN=200010;

intn,m;

intv[N],w[N];

intf[N];

intmain()

{

cinnm;

intcnt=1;

for(inti=1;i=n;i++)

{

inta,b,s;

cinabs;

intk=1;

while(k=s)

{

v[cnt]=a*k;

w[cnt]=b*k;

s-=k;

k*=2;

cnt++;

}

if(s0)

{

v[cnt]=s*a;

w[cnt]=s*b;

cnt++;

}

}

for(inti=1;i=cnt;i++)

{

for(intj=m;j=v[i];j--)

{

f[j]=max(f[j],f[j-v[i]]+w[i]);

}

}

coutf[m]\n;

return0;

}

Java

importjava.util.Scanner;

publicclassMain{

staticfinalintN=200010;

staticintn,m;

staticint[]v=newint[N],w=newint[N];

staticint[]f=newint[N];

publicstaticvoidmain(String[]args){