96、小蓝的神秘行囊.docx

解题思路

这道题是一种常见的动态规划问题，又称为“二维费用背包问题”。这个问题的关键在于我们需要处理两种限制条件：背包的容量和背包能承受的最大重量。这两种条件都需要考虑进我们的状态定义和状态转移方程中。

状态定义

我们使用?f[i][j][k]?来表示，对于前?i?件物品，考虑到背包的容量不超过?j，并且背包的总重量不超过?k?时，我们能够得到的最大价值。

状态转移

对于每一件物品，我们有两种选择：

不拿这件物品。这种情况下，f[i][j][k]=f[i?1][j][k]，即当前的最大价值等于前?i?1?件物品在相同容量和重量限制下的最大价值。

拿这件物品。这种情况下，我们需要确保背包的容量?j?大于物品的体积?v[i]，并且背包的总重量?k?大于物品的重量?m[i]。如果这两个条件都满足，我们就可以选择这件物品，然后从背包的剩余容量和剩余重量中扣除物品的体积和重量，得到f[i?1][j?v[i]][k?m[i]]+w[i]。

我们的目标是找到一个使f[i][j][k]?最大的选择，所以我们使用?max?函数来选择上述两种情况中的最大值。

分析答案状态

在我们处理完所有的物品之后，f[n][V][M]?就是我们的最终答案，表示在容量为?V，重量为?M?的限制下，我们能够得到的最大总价值。

这道题的状态定义和状态转移都比较直观，核心思想是通过动态规划来优化我们的选择策略，确保我们在满足背包容量和重量限制的情况下，能够得到最大的总价值。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

constintN=1100;

intn,V,M;

intv[N],m[N],w[N];

intf[N][N/10][N/10];

intmain()

{

ios_base::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

cinnVM;

for(inti=1;i=n;++i)cinv[i]m[i]w[i];

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

for(intj=1;j=V;++j){

for(intk=1;k=M;++k){

f[i][j][k]=f[i-1][j][k];

if(v[i]=jm[i]=k)f[i][j][k]=max(f[i][j][k],f[i-1][j-v[i]][k-m[i]]+w[i]);

}

}

}

coutf[n][V][M]\n;

return0;

}

Java

imporjava.io.BufferedReader;

importjava.io.IOException;

importjava.io.InputStreamReader;

importjava.util.StringTokenizer;

publicclassMain{

staticfinalintN=1100;

staticintn,V,M;

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

staticint[][][]f=newint[N][N/10][N/10];

publicstaticvoidmain(String[]args)throwsIOException{

BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));

StringTokenizerst=newStringTokenizer(br.readLine());

n=Integer.parseInt(st.nextToken());

V=Integer.parseInt(st.nextToken());

M=Integer.parseInt(st.nextToken());

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

st=newStringToke