88、小兰的神秘礼物.docx

解题思路

这道题目实际上是经典的「0-1背包」问题的一种变形。我们需要找出一个或多个小物件，使得它们的体积总和最接近箱子的容量，从而使得箱子的剩余空间最小。实际上每个箱子的价值和体积是相等的，这个问题可以通过动态规划的方法来解决。

状态定义

在这个问题中，我们可以定义一个一维动态规划数组?f，其中?f[i]?表示箱子容量为?i?时，能够装入物品的最大体积。初始化时，数组?f?的所有元素都为?0，表示在没有任何物品可选的情况下，任何容量的箱子都只能装入?0?的体积。

状态转移

我们需要对每一个小物件进行遍历，对于第?i?个物件，我们考虑在箱子容量为?j（j?从?t?到?v[i]）的情况下，如果不装入这个物品，那么能装入的最大体积就是?f[j]；如果装入这个物品，那么能装入的最大体积就是?f[j-v[i]]+v[i]。我们取这两种情况的最大值，作为?f[j]?的新值。这就是我们的状态转移方程。

需要注意的是，我们在遍历?j?时，需要从大到小进行遍历，这是因为每个物品只能使用一次（即「0-1」背包问题），如果我们从小到大遍历，那么在计算?f[j]?的时候，f[j-v[i]]?可能已经被我们在这一轮中更新过，相当于物品?i?被使用多次，这与我们的问题设定不符。

答案状态

我们想要得到的是箱子的最小剩余空间，根据我们的状态定义，箱子的最小剩余空间就是?t-f[t]，其中?t?是箱子的容量。

解题步骤

初始化一维动态规划数组?f，所有元素都为?0。

对每一个小物件进行遍历，对于每一个物品，从?t?到?v[i]?遍历?j，更新?f[j]?的值为?max(f[j],f[j-v[i]]+v[i])。

输出?t-f[t]，即为箱子的最小剩余空间。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

constintN=20010;

intf[N],v[N];

intmain(){

intt,n;

cintn;

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

cinv[i];

}

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

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

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

}

}

coutt-f[t]\n;

return0;

}

Java

importjava.util.Scanner;

publicclassMain{

staticintN=20010;

staticint[]f=newint[N];

staticint[]v=newint[N];

publicstaticvoidmain(String[]args){

Scannersc=newScanner(System.in);

intt=sc.nextInt();

intn=sc.nextInt();

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

v[i]=sc.nextInt();

}

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

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

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

}

}

System.out.println(t-f[t]);

}

}

Python

N=20010

f=[0]*N

v=[0]*N

t=int(input())

n=int(input())

foriinrange(1,n+1):

v[i]=int(input())

foriinrange(1,n+1):

forjinrange(t,v[i]-1,-1):

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

print(t-f[t])