题解 P1049 【装箱问题】

· · 题解

这题拿到手我就想着可不可以枚举，但没多久就发现这样会超时。

由于DP我还不会，所以作为一支konjac的我就用一种叫做记忆化搜索的与DP雷同但实现较简单的算法。

于是，我记dfs(x,y)表示选取前x个箱子，容量为y时装入箱子的最大体积。

所以如果y+a[x]<=n，就表示第x个箱子可以装进去，那么装进去后的最大值就是dfs(x+1,y+a[i])

而每一种情况，第x个箱子都可以不装入所以不装入的最大值为dfs(x+1,y)

所以dfs(x,y)=max(dfs(x+1,y),s)

其中若y+a[x]<=n，s=dfs(x+1,y+a[i]) 否则s=0

但这只是普通的搜索，为了达成"记忆化"我们就要开一个f二维数组来记录已经搜索过的状态。

f数组初始值为-1，在进行dfs(x,y)时若f[x][y]!=-1那就说明这一状态已经被搜索过，直接返回f[x][y]即可。

否则就搜索，在最后返回值之前将搜索到的值存入f数组中。

这样我们就完成了一个记忆化搜索的过程。

下面上AC代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int v,n,a[35],f[35][20005];
inline int max(int x,int y){return x>y?x:y;}
inline int dfs(int x,int y){
    if(x==n+1) return y;
    if(f[x][y]!=-1) return f[x][y];
    int xx=0,yy=dfs(x+1,y);
    if(y+a[x]<=v) xx=dfs(x+1,y+a[x]);
    f[x][y]=max(xx,yy);
    return f[x][y];
}
int main(){
    scanf("%d",&v); scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=v;j++)
            f[i][j]=-1;
    printf("%d\n",v-dfs(1,0));
    return 0;
}