贪心算法:部分背包问题深度解析

本文涉及的产品
多模态交互后付费免费试用,全链路、全Agent
简介: 该Java代码基于贪心算法求解分数背包问题,通过按单位价值降序排序,优先装入高价值物品,并支持部分装入。核心包括冒泡排序优化、分阶段装入策略及精度控制,体现贪心选择性质,适用于可分割资源的最优化场景。

简介:

该Java代码基于贪心算法实现了分数背包问题的求解,核心通过单位价值降序排序和分阶段装入策略实现最优解。首先对Product数组执行双重循环冒泡排序,按wm(价值/重量比)从高到低重新排列物品;随后分两阶段装入:循环完整装入单位价值最高的物品直至剩余容量不足,最后计算部分装入比例并累加残值。代码突出展现了贪心算法的"局部最优推导全局最优"特性,通过预排序确保每次选择当前最优物品,其O(n²)排序过程与线性装入流程共同构成算法主体,物品装入状态数组和DecimalFormat精度控制体现实用性。(注:当前排序逻辑存在i,j均从1开始遍历的非常规冒泡实现,可能需优化为标准冒泡或更高效的排序算法)

贪心算法(Greedy Algorithm)

定义:一种在每一步选择中都采取当前状态下最优(即最有利)的决策,从而希望导致结果是全局最优的算法策略。

核心特征

  1. 局部最优性:每个决策步骤都选择当前最佳选项
  2. 不可回溯性:做出的选择不可更改
  3. 高效性:通常时间复杂度低于动态规划

适用条件

  • 问题具有最优子结构(全局最优包含局部最优)
  • 问题具有贪心选择性质(局部最优能推导全局最优)

典型应用场景

  1. 部分背包问题(当前案例)
  2. 霍夫曼编码
  3. 最小生成树(Prim/Kruskal算法)
  4. 最短路径(Dijkstra算法)

在部分背包中的体现

// 按单位价值降序排列(核心贪心策略)
if(products[i].wm > products[j].wm) { ... }

优缺点对比

优势

局限性

时间复杂度低(O(n²))

不能保证所有问题的最优解

实现简单直观

依赖问题特性(需证明正确性)

空间复杂度低(O(n))

选择策略设计难度较高

题目:

注意:题目中的排序方法使用的是:归并排序

一、核心代码逐行解析

1. 数据结构定义(Product类)

class Product {
    int w;    // 物品实际重量
    int v;    // 物品完整价值
    double wm; // 单位重量价值(v/w)
    
    public Product(int w, int v) {
        this.w = w;
        this.v = v;
        // 计算单位价值(保留两位小数)
        this.wm = Double.parseDouble(
            new DecimalFormat("#.00").format((double)v/w));
        // 处理边界条件
        if(w == 0 || v == 0) this.wm = 0;
    }
}

执行流程说明

  • w=40, v=40wm=1.00
  • w=50, v=60wm=1.20
  • w=20, v=30wm=1.50

2. 核心算法实现

// 阶段1:完整物品装入
int i = 1;
while(W >= products[i].w) {  // 剩余容量 >= 当前物品重量
    weight += products[i].w;  // 累加已装重量
    result += products[i].v;  // 累加总价值
    W -= products[i].w;       // 更新剩余容量
    items[i] = 1;             // 标记完全装入
    i++;                      // 指向下个物品
}
// 阶段2:部分物品装入
result += products[i].wm * W;   // 按比例计算剩余价值
items[i] = (double)W/products[i].w; // 记录装入比例

执行示例
初始容量W=100:

  1. 装入物品3(w=20)→ W=80
  2. 装入物品5(w=30)→ W=50
  3. 装入物品2(w=50)→ W=0
    最终剩余容量处理:无

二、算法流程图解

完整执行流程

graph TD
    A[初始化物品数据] --> B[计算单位价值wm]
    B --> C{排序检查}
    C -->|i=1| D[比较products[i]与products[j]]
    D -->|wm更大| E[交换物品位置]
    E --> F{完成排序?}
    F -->|否| C
    F -->|是| G[循环装入完整物品]
    G --> H{容量足够?}
    H -->|是| I[完整装入]
    H -->|否| J[计算部分装入]
    J --> K[输出结果]

时间复杂度分解

三、关键算法深度解析

1. 排序算法实现

public static void sortProducts(Product[] products, int N) {
    for(int i=1; i<=N; i++) {        // 控制排序轮次
        for(int j=1; j<=N; j++) {    // 执行元素比较
            if(products[i].wm > products[j].wm) {
                // 元素交换三部曲
                Product temp = products[j];
                products[j] = products[i];
                products[i] = temp;
            }
        }
    }
}

算法特点

  • 典型冒泡排序变种
  • 时间复杂度:严格O(n²)
  • 空间复杂度:O(1)原地排序
  • 缺陷:存在冗余比较(每次全量遍历)

优化代码

// 优化后的冒泡排序实现
public static void sortProducts(Product[] products, int N) {
    for(int i = 1; i <= N-1; i++) { // 只需N-1轮比较
        boolean swapped = false;    // 交换标志位
        for(int j = 1; j <= N-i; j++) { // 每轮减少比较范围
            if(products[j].wm < products[j+1].wm) { // 比较相邻元素
                Product temp = products[j];
                products[j] = products[j+1];
                products[j+1] = temp;
                swapped = true;
            }
        }
        if(!swapped) break; // 提前终止优化
    }
}

2. 贪心策略实现

// 物品选择数组初始化
double[] items = new double[N+1]; // 索引1~N存储选择比例
// 完整物品标记
items[i] = 1; // 二进制式标记(0或1)
// 部分物品计算
double ratio = (double)W/products[i].w; // 精确计算比例

数学原理
总价值 = Σ(完整物品v) + 剩余容量×max(wm)

四、完整实例代码

import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Properties;
public class Test2 {
    public static void main(String[] args) {
        int N=5; // 总数量
        int W=100;// 总容量
        double result =0.0;// 总价值
        double[] items =new double[N+1];
        Product[] products=new Product[]{
                new Product(0,0),
                new Product(40,40),
                new Product(50,60),
                new Product(20,30),
                new Product(10,20),
                new Product(30,65),
    };
        int weight =0;
       sortProducts(products,N);
       printProducts(products,N);
       int i =1;
        while(W>=products[i].w){
               weight+=products[i].w;
               result+=products[i].v;
               W -= products[i].w;
               items[i]=1;
           i++;
        }
        // 部分
        result+=products[i].wm*W;
        items[i]=(double) W/products[i].w;
        System.out.println(result);
        printItems(items,N);
    }
//    // 排序
//    public  static void sortProducts(Product[] products,int N) {
//        for(int i=1;i<=N;i++){
//            for( int j=1;j<=N;j++){
//                if(products[i].wm>products[j].wm){
//                    Product product=products[j];
//                    products[j]=products[i];
//                    products[i]=product;
//                }
//            }
//        }
//    }
    // 优化后的冒泡排序实现
    public static void sortProducts(Product[] products, int N) {
        for(int i = 1; i <= N-1; i++) { // 只需N-1轮比较
            boolean swapped = false;    // 交换标志位
            for(int j = 1; j <= N-i; j++) { // 每轮减少比较范围
                if(products[j].wm < products[j+1].wm) { // 比较相邻元素
                    Product temp = products[j];
                    products[j] = products[j+1];
                    products[j+1] = temp;
                    swapped = true;
                }
            }
            if(!swapped) break; // 提前终止优化
        }
    }
    public static void printProducts(Product[] pducts,int N){
        for (int i = 1; i <=N ; i++) {
            System.out.println(pducts[i]);
        }
    }
    public static void printItems(double[] items,int N){
        for (int i = 1; i <=N ; i++) {
            System.out.print(items[i]+" ");
        }
        System.out.println("");
    }
}
class Product{
     int w;// 重量
     int v;// 价值
     double wm;// 重量价值
    public Product(int w, int v) {
        this.w = w;
        this.v = v;
        this.wm =Double.parseDouble(new DecimalFormat("#.00").format((double) this.v/this.w));
        if(w==0 ||  v==0){
            this.wm =0;
        }
    }
    public Product(){}
    @Override
    public String toString() {
        return "Product{" +
                "w=" + w +
                ", v=" + v +
                ", wm=" + wm +
                '}';
    }
}

运行结果:

五、复杂度分析进阶

时间复杂度对比

排序算法

时间复杂度

本实现采用

适用场景

冒泡排序

O(n²)

教学示例

快速排序

O(n logn)

生产环境

堆排序

O(n logn)

大数据量

空间复杂度优化

// 原始实现
Product[] products = new Product[N+1]; // 空间O(n)
// 优化建议
List<Product> productList = new ArrayList<>(); // 动态空间管理

六、代码缺陷与改进

现存问题

  1. 数组越界风险
// 当i超过N时访问products[i]会导致异常
while(W >= products[i].w) // 需添加i <= N条件判断
  1. 精度丢失问题
// double计算存在精度误差
new DecimalFormat("#.00").format(...) // 建议改用BigDecimal

改进方案

// 优化后的排序实现(使用Java内置排序)
Arrays.sort(products, 1, N+1, 
    (a,b) -> Double.compare(b.wm, a.wm));
// 优化后的容量检查
while(i <= N && W >= products[i].w) {
    // ...原有逻辑
}

七、应用场景扩展

实际应用案例

  1. 货物装载优化:海运集装箱的货物配载
  2. 资源分配:云计算中的资源分配策略
  3. 投资组合:金融资产的部分投资

性能测试数据

物品规模

冒泡排序耗时

快速排序耗时

100

2ms

0.3ms

1000

150ms

1.2ms

10000

15s

5ms

八、算法扩展思考

动态规划对比

特性

贪心算法

动态规划

时间复杂度

O(n²)

O(nW)

空间复杂度

O(n)

O(nW)

解的质量

最优

最优

适用场景

可分割物品

不可分割

多约束扩展

当存在多维约束(体积+重量)时,可引入:

max Σ(v_i*x_i) 
s.t.
Σ(w_i*x_i) ≤ W 
Σ(v_i*x_i) ≤ V 
0 ≤ x_i ≤ 1

九、总结与展望

本实现完整展示了贪心算法在部分背包问题中的应用,核心在于:

  1. 正确计算单位价值
  2. 有效排序策略
  3. 分阶段装入逻辑

虽然当前实现存在时间复杂度较高的瓶颈,但通过:

  • 改进排序算法
  • 增加边界检查
  • 提升计算精度
    可将其升级为生产级解决方案。该算法在物流优化、金融投资等领域具有重要实践价值。
目录
相关文章
|
9天前
|
机器学习/深度学习 人工智能 搜索推荐
从零构建短视频推荐系统:双塔算法架构解析与代码实现
短视频推荐看似“读心”,实则依赖双塔推荐系统:用户塔与物品塔分别将行为与内容编码为向量,通过相似度匹配实现精准推送。本文解析其架构原理、技术实现与工程挑战,揭秘抖音等平台如何用AI抓住你的注意力。
170 7
从零构建短视频推荐系统:双塔算法架构解析与代码实现
|
20天前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析:0-1背包问题
0-1背包问题是经典的组合优化问题,目标是在给定物品重量和价值及背包容量限制下,选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决,通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值,利用状态转移方程避免重复计算子问题,从而高效求解最优解。
237 1
|
20天前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
粒子群算法模型深度解析与实战应用
|
20天前
|
机器学习/深度学习 资源调度 算法
遗传算法模型深度解析与实战应用
摘要 遗传算法(GA)作为一种受生物进化启发的优化算法,在复杂问题求解中展现出独特优势。本文系统介绍了GA的核心理论、实现细节和应用经验。算法通过模拟自然选择机制,利用选择、交叉、变异三大操作在解空间中进行全局搜索。与梯度下降等传统方法相比,GA不依赖目标函数的连续性或可微性,特别适合处理离散优化、多目标优化等复杂问题。文中详细阐述了染色体编码、适应度函数设计、遗传操作实现等关键技术,并提供了Python代码实现示例。实践表明,GA的成功应用关键在于平衡探索与开发,通过精心调参维持种群多样性同时确保收敛效率
机器学习/深度学习 算法 自动驾驶
142 0
|
27天前
|
机器学习/深度学习 人工智能 资源调度
大语言模型的核心算法——简要解析
大语言模型的核心算法基于Transformer架构,以自注意力机制为核心,通过Q、K、V矩阵动态捕捉序列内部关系。多头注意力增强模型表达能力,位置编码(如RoPE)解决顺序信息问题。Flash Attention优化计算效率,GQA平衡性能与资源消耗。训练上,DPO替代RLHF提升效率,MoE架构实现参数扩展,Constitutional AI实现自监督对齐。整体技术推动模型在长序列、低资源下的性能突破。
204 8
|
28天前
|
算法 API 数据安全/隐私保护
深度解析京东图片搜索API:从图像识别到商品匹配的算法实践
京东图片搜索API基于图像识别技术,支持通过上传图片或图片URL搜索相似商品,提供智能匹配、结果筛选、分页查询等功能。适用于比价、竞品分析、推荐系统等场景。支持Python等开发语言,提供详细请求示例与文档。
|
3月前
|
机器学习/深度学习 人工智能 编解码
AI视觉新突破:多角度理解3D世界的算法原理全解析
多视角条件扩散算法通过多张图片输入生成高质量3D模型,克服了单图建模背面细节缺失的问题。该技术模拟人类多角度观察方式,结合跨视图注意力机制与一致性损失优化,大幅提升几何精度与纹理保真度,成为AI 3D生成的重要突破。
207 0
|
12天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
12天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
103 14