题解P1049【装箱问题】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 1.3k | 阅读时长 ≈ 1 分钟

看到好多大佬都用动规，这题数据范围太水了(n<=30)于是本蒟蒻先来发篇dfs

深搜思路：

把n个物品两种可能（取与不取）都搜一遍，得到的最小体积就是答案

具体解释看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
int v,n,w[40],minx=INT_MAX;//minx存放最小体积，初始赋最大值
void dfs(int volume,int pointer)//volume代表当前体积
//pointer指示第pointer个物品
{
    if(volume<0) return;//首先需要判断如果体积<0就退出
    if(pointer>n)//如果n个物品都搜过了
    {
        if(volume<minx)//判断当前体积是否小于最小体积
            minx=volume;//是的话更新最小体积
        return;
    }
    if(volume==0)//小小的剪枝，如果当前体积已经为0了，那么不可能有更优解
    {
        minx=0;
        return;
    }
    dfs(volume-w[pointer],pointer+1);//取该件物品
    dfs(volume,pointer+1);//不取该件物品
}
int main()
{
    scanf("%d%d",&v,&n);
    for(int i=1; i<=n; i++) scanf("%d",&w[i]);
    dfs(v,1);
    printf("%d",minx);//minx存放的即为答案
    return 0;
}

但是如果数据范围加大了话。。。

其实本题就是把0-1背包中物品的价值与体积画了个等号，于是本题就变成了一道0-1

背包模板题

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int w[31],f[20010];
int main()
{
    int v,n;
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++)
      scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
      for(int j=v;j>=w[i];j--)
        if(f[j]<f[j-w[i]]+w[i])
          f[j]=f[j-w[i]]+w[i];//状态转移方程
    printf("%d",v-f[v]);//最后用体积减去最优解
    return 0;
}