[NOIP2001 普及组] 装箱问题

题目描述

有一个箱子容量为 $V$，同时有 $n$ 个物品，每个物品有一个体积。

现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 $V$，表示箱子容量。

第二行共一个整数 $n$，表示物品总数。

接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。

输出格式

  • 共一行一个整数，表示箱子最小剩余空间。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
24
6
8
3
12
7
9
7

样例输出 #1

1
0

提示

对于 $100\%$ 数据，满足 $0<n \le 30$，$1 \le V \le 20000$。

【题目来源】

NOIP 2001 普及组第四题

题解

题目解析

一个简化的01背包问题,今天刚学的背包问题,作为例题所作.这个问题如果按照一个一个列的话可能到$2^{30}$个可能,事实上我们仅需考虑其前面最多可能组成的可能性.

举一个例子:

1
2
3
4
5
6
7
8
9
10
11
12
背包大小为10,其中有5个物品,其重量为:1 2 3 4 5.
我们分开情况讨论:
- 1:0,1
当仅有一个重量为1的物品时,我们只能组成0,1的重量的物品.
- 1->2:0,1,2,3
当在第一个物品的基础之上时,我们可以在第一个物品的基础上进行组合,也就是可能组成:
0,1,2,3这四种情况,其组合方法:0+2/1+2->2/3或直接一个2.
- 1,2->3:0,1,2,3,4,5,6
当在前两个物品的基础之上时,可能的组成为:
0,1,2,3,4,5,6这七种情况,其组合方法可以是:0+3/1+3/2+3/3+3->3/4/5/6或单个蹦或啥也不选.
以此类推,我们最后可以组成:
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15;

最后我们可以得到状态转移方程(f[i][j]存的是bool类型):

文字解释:前i个数字组成价值为j的背包=前i-1个数字组成价值为j的背包||前i-1个数字组成价值为j-a[i]的背包.

举个例子:

1
2
3
4
5
背包大小为20,其中有3个物品,其重量为:1 5 8.
从i=2开始:
f[1][0] = 1显然
f[1][1] = 1显然
f[2][6] = f[1][6-5]<->f[1][1] = 1也就是要想组成重量为6的背包需要先组成i=1情况下重量为1的背包才可以.

AC代码

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
30
31
#include <iostream>
using namespace std;

int f[2][20010],a[40];

int main(){
    int v,n;
    cin >> v >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    f[0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=v;j++){
            if(j < a[i]){
                f[i%2][j] = f[(i-1)%2][j];
            }else{
                f[i%2][j] = f[(i-1)%2][j] || f[(i-1)%2][j-a[i]];
            }
        }
    }
    int ans = 0;
    for(int i=v;i>=0;i--){
        if(f[n%2][i]){
            ans = i;
            break;
        }
    }
    cout << v - ans;
    return 0;
}

Remark

  • 关于这块代码

    1
    2
    3
    4
    5
    6
    7
    for(int j=0;j<=v;j++){
        if(j < a[i]){
            f[i%2][j] = f[(i-1)%2][j];
        }else{
            f[i%2][j] = f[(i-1)%2][j] || f[(i-1)%2][j-a[i]];
        }
    }

    这块有两种解释:

    • 如果j < a[i]那么j-a[i]会小于0,所以需要分开情况讨论
    • j < a[i]的部分中需要把之前存的f[i-1][j]的情况原封不动放到f[i][j]中,j >= a[i]的部分既需要原封不动的存下来,也需要考虑j-a[i]的情况.

  • i的存在仅依靠与i-1的存在,i+1的存在与i-1并无关系,所以仅需要i=2就可以全部存下来了,所以用了i%2和(i-1)%2就可以了.

  • 当然，我们可以对二维数组进一步优化,直接使用一维数组进行滚动刷新.

    1
    2
    3
    4
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=v;j++)
            f[j] = f[j] || f[j-a[i]];
    }

    但是这个代码会出现一个bug:

    1
    2
    3
    4
    5
    6
    假如背包大小为20,其中有3个物品,其重量为:1 5 8.
    当i=2时:
    for(int j=a[i];j<=v;j++)会不断循环:
    f[6] = f[1+5] = 1; f[11] = f[6+5] =1; f[17] = f[11+5] = 1;
    造成其能组成 6(1+5) 11(1+5+5) 17(1+5+5+5) ...的情况,也就是加了多次.
    实际上它仅能组成 6 (1+5)的背包,多出去的都是加重了的情况.

    如何解决呢?这就用到了一个小技巧:

    倒序递归:

    1
    2
    3
    4
    for(int i=1;i<=n;i++){    
        for(int j=v;j>=a[i];j--)        
            f[j] = f[j] || f[j-a[i]];
    }

    手动走一遍递归,看看是不是不会出现重复的情况了?

    AC代码:

    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
    #include <iostream>
    using namespace std;

    int f[20010],a[40];

    int main(){
        int v,n;
        cin >> v >> n;
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        f[0] = 1;
        for(int i=1;i<=n;i++){    
        	for(int j=v;j>=a[i];j--)        
            	f[j] = f[j] || f[j-a[i]];
    	}
        int ans = 0;
        for(int i=v;i>=0;i--){
            if(f[i]){
                ans = i;
                break;
            }
        }
        cout << v - ans;
        return 0;
    }

Others

艹,过几天就要省赛了,结果背包还刚学.啊?我刚大一啊,那没事了.