贪心一【深基12.例1】部分背包问题详解

4 50
10 60
20 100
30 120
15 45
1
2
3
4
5

240.00
1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        float N = sc.nextFloat();
        float T = sc.nextFloat();
        int i;
        float m[] = new float[1000];
        float v[] = new float[1000];
        float x[] = new float[1000];
        for (i = 0; i < N; i++)
        {
            m[i] = sc.nextFloat();
            v[i] = sc.nextFloat();
        }
        System.out.println(String.format("%.2f", knapsack(T, m, v, x)));
    }
   
    public static float knapsack(float T, float m[], float v[], float x[]){
        int n;
        n = m.length;
        int i, j;
        float temp1, temp2;
        float opt = 0;

        for (i = 0; i < n; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if ((v[i] / m[i]) < (v[j] / m[j]))
                {
                    temp1 = m[i];
                    m[i] = m[j];
                    m[j] = temp1;
                    temp2 = v[i];
                    v[i] = v[j];
                    v[j] = temp2;
                }
            }
        }
        for ( i = 0; i < n; i++)
        {
            x[i] = 0;
        }
        for (j = 0; j < n; j++)
        {
            if (m[j] > T)break;

            x[j] = 1;
            opt = opt + v[j];
            T = T - m[j];
        }
        if (j

• 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
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62

七、步骤及解析

本题可以使用背包问题的贪心算法实现，最重要的就是掌握代码中定义的knapsack函数，相当于一个模板，可以在其它题目中套用。

（1）knapsack函数的分析

• float T：背包剩余的承重量
• float m[]： 物品的重量
• float v[]：物品的价值
• float x[]：将问题的最优解存入x[]这个未使用过的数组中
• 函数的返回值：浮点数opt（装入背包的总价值），并且题目中样例输出是保留了两位小数，记得在最后打印的时候保留两位小数，否则会显示答案错误！
• 注意：这些量都需要是浮点型，因为你无法确定金币不需要分割。使用浮点型方便拆分。

（2）knapsack函数实现的步骤

①进行预备工作：定义了三个int型变量，三个float型变量

• n表示金币的堆数
• 除了n,i,j是整型，其他都是浮点型
• 定义了变量opt来记录总价值，并将其初始化为0

        int n;
        n = m.length;
        int i, j;
        float temp1, temp2;
        float opt = 0;
1
2
3
4
5

②进行排序

• 将不同堆的金币，按照金币重量价值比，即单位重量价值（v/m）从大到小排序，v/m越大，代表越有价值，更应该被优先选择。
• 通过使用两个for循环嵌套，将前后两堆金币的价值比进行比较，如果后面的j下标对应的价值比大于当前i下标对应的价值比，则利用中间变量temp1，temp2将v[i]与v[j]进行交换，m[i]与m[j]进行交换。

        for (i = 0; i < n; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if ((v[i] / m[i]) < (v[j] / m[j]))
                {
                    temp1 = m[i];
                    m[i] = m[j];
                    m[j] = temp1;
                    temp2 = v[i];
                    v[i] = v[j];
                    v[j] = temp2;
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

③初始化解集x

• x = {x1,x2,x3,…,xn} = {0，0，0，…，0}

        for ( i = 0; i < n; i++)
        {
            x[i] = 0;
        }
1
2
3
4

④将可以整堆带走，无需分割的金币堆装入解集x[]

• 结束这个循环的条件是，当当前要装入的金币堆的重量>当前背包剩余的承重量，即不能整堆带走，此时循环结束进入步骤⑤（注意：循环的结束条件要写在循环的最前面）

        for (j = 0; j < n; j++)
        {
            if (m[j] > T)break;

            x[j] = 1;
            opt = opt + v[j];
            T = T - m[j];//T此时表示背包剩余容量
        }
1
2
3
4
5
6
7
8

⑤将无法整堆带走，需分割的金币堆装入解集x[]

• 对于x[j] = T / m[j]，意思是若第j堆金币可以完整装入，则x[j]记为1，若装入一半，则记为1/2
• 对于 T / m[j]，意思是背包剩余承载量与金币堆重量的比例，并且 T / m[j]<1
• 对于 opt = opt + T * (v[j] / m[j])，意思是总价值=上面计算过了的可以整堆带走，无需分割的金币堆的总价值 + 当前剩余的承重量T * 当前金币堆的单位价格v[j] / m[j]

        if (j