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

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

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

【深基12.例1】部分背包问题

一、题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N ( N ≤ 100 ) N(N \le 100) N(N≤100) 堆金币，第 i i i 堆金币的总重量和总价值分别是 m i , v i ( 1 ≤ m i , v i ≤ 100 ) m_i,v_i(1\le m_i,v_i \le 100) mi​,vi​(1≤mi​,vi​≤100)。阿里巴巴有一个承重量为 T ( T ≤ 1000 ) T(T \le 1000) T(T≤1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

二、输入格式

第一行两个整数 N , T N,T N,T。

接下来 N N N 行，每行两个整数 m i , v i m_i,v_i mi​,vi​。

三、输出格式

一个实数表示答案，输出两位小数

四、样例输入

4 50
10 60
20 100
30 120
15 45

五、样例输出

240.00

六、代码

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<n){x[j] = T / m[j];opt = opt + T * (v[j] / m[j]);}return opt;}
}

七、步骤及解析

本题可以使用背包问题的贪心算法实现，最重要的就是掌握代码中定义的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;

②进行排序

• 将不同堆的金币，按照金币重量价值比，即单位重量价值（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;}}}

③初始化解集x

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

        for ( i = 0; i < n; i++){x[i] = 0;}

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

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

        for (j = 0; j < n; j++){if (m[j] > T)break;x[j] = 1;opt = opt + v[j];T = T - m[j];//T此时表示背包剩余容量}

⑤将无法整堆带走，需分割的金币堆装入解集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<n){x[j] = T / m[j];opt = opt + T * (v[j] / m[j]);}

⑥函数返回已经装入的总价值（opt）

return opt;