部分背包问题(贪心基础)

简介: 有n个物体,第i个物体重量为w[i] 价值为v[i]。在总重量不超过C的情况下让总价值尽量高.取一个物品必须全取,价值和重量按比例计算【分析】 贪心策略:优先拿“价值除以重量的值”最大的,重量和小于等于C#...

有n个物体,第i个物体重量为w[i] 价值为v[i]。在总重量不超过C的情况下让总价值尽量高.取一个物品必须全取,价值和重量按比例计算

【分析】
贪心策略:优先拿“价值除以重量的值”最大的,重量和小于等于C

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Box {
    double w;   //重量 
    double v;   //价值 
}; 

//排序比较函数,以物品的价值/重量比值降序排序 
bool cmp(Box a, Box b) {
    if (a.v/a.w > b.v/b.w) {
        return true;
    }
    return false;
}

/*
    贪心算法装载 

    vector采用引用传递,也可以使用指针传递 
    引用传递相对比较安全 
    和数组不同 
    如果值传递是无法影响到实参r的,而且实参给
    形参赋值时会调用拷贝构造函数浪费资源 

    数组传递的是首地址 
*/
void loading(Box *box, vector<Box> &r,int c,int n) {
    for (int i = 0; i < n; i++) {
        if (c-box[i].w >= 0) {
            c -= box[i].w;
            r.push_back(box[i]);
        } 
    }
}


int main() {
    struct Box box[] = {{10,12},{9,9},{11,7},{12,9},{6,8},{3,4}};
    double c = 30; //承载重量

    sort(box,box+6,cmp);

    vector<Box> request;

    loading(box,request,c,6);

    for (int i = 0; i < request.size(); i++) {
        cout << "w:"<<request[i].w<< " v:" << request[i].v << endl;
    }


    return 0;
}
目录
相关文章
|
机器学习/深度学习 C语言
【C语言必知必会 | 子系列第五篇】深入剖析循环结构(1)
【C语言必知必会 | 子系列第五篇】深入剖析循环结构(1)
528 0
【C语言必知必会 | 子系列第五篇】深入剖析循环结构(1)
|
搜索推荐 机器学习/深度学习 算法
如何增加用户的参与感?交互式推荐来了!
一方面,互动能让用户感受到更多的参与感,并能一定程度上干预推荐结果,而不只是被动接受推荐结果;另一方面,系统通过与用户的互动能更加了解用户的偏好,从而提升推荐效果。那么,我们是如何让用户和推荐系统互动起来的呢?且看下文。
6083 0
|
机器学习/深度学习 人工智能 边缘计算
大模型在医疗领域的应用
🌟蒋星熠Jaxonic,AI开发者,深耕医疗大模型领域。见证代码如何重塑医疗:从影像分析到智能诊断,从药物研发到临床决策。分享技术实践与行业洞察,探索AI赋能健康的时代变革。
大模型在医疗领域的应用
|
JSON 搜索推荐 算法
利用API提升电商用户体验:个性化推荐系统
在电商竞争激烈的当下,个性化推荐系统成为提升用户粘性与转化率的关键。本文详解如何通过API集成高效接入先进推荐算法,实现实时精准推荐,优化用户体验,提升业务增长。
|
10月前
|
存储 人工智能 安全
AI智能体的开发费用
2026年AI智能体开发成本两极分化:低代码工具使简单Agent成本降至5千-2万元,而复杂企业级系统仍需30万以上。费用涵盖开发、API、算力及维护,建议从中级智能体切入,结合开源平台与工作流模式降本增效。#AI智能体 #降本策略
|
存储 缓存 运维
阿里云服务器经济型e与通用算力型u1实例各自性能、适用场景区别及选择参考
在选择阿里云服务器实例规格时,经济型e实例和通用算力型u1实例因其高性价比和广泛适用性,备受个人开发者、中小企业的青睐。在同地域、相同配置的情况下,经济型e和通用算力型u1实例的价格相对于其他实例规格要低一些,很多个人和初创企业用户都会优先考虑选择这两个实例规格的云服务器,那么它们之间有什么区别?各自的性能、适用场景上有何区别?我们应该如何选择呢?本文将详细解析这两款实例的性能特点、适用场景、价格优势及购买建议,帮助用户更好地理解并选择合适的云服务器实例。
942 17
|
搜索推荐 NoSQL Java
微服务架构设计与实践:用Spring Cloud实现抖音的推荐系统
本文基于Spring Cloud实现了一个简化的抖音推荐系统,涵盖用户行为管理、视频资源管理、个性化推荐和实时数据处理四大核心功能。通过Eureka进行服务注册与发现,使用Feign实现服务间调用,并借助Redis缓存用户画像,Kafka传递用户行为数据。文章详细介绍了项目搭建、服务创建及配置过程,包括用户服务、视频服务、推荐服务和数据处理服务的开发步骤。最后,通过业务测试验证了系统的功能,并引入Resilience4j实现服务降级,确保系统在部分服务故障时仍能正常运行。此示例旨在帮助读者理解微服务架构的设计思路与实践方法。
1243 17
|
Linux API 图形学
OpenGL生态中的GL, GLU, GLUT, GLX, GLEW, GLEE和GLEXT详解
该文介绍了OpenGL生态系统中的关键组件,包括GL(基础绘图API)、GLU(提供辅助函数)、GLUT(窗口管理和事件处理)、GLX(X Window系统上的OpenGL扩展)、GLEW和GLEE(动态查询和封装OpenGL扩展)以及GLEXT(OpenGL扩展集合)。这些库和工具协同工作,帮助开发者构建跨平台的图形应用程序,提升兼容性与功能。理解它们的作用对优化OpenGL编程至关重要。
|
JSON 缓存 NoSQL
重新更新VScode配置(C/C++)——负责任、手把手教学,亲测有效
对于C/C++的编程环境来说,目前我们所接触到的、所用到的,除了vim以外,大众用的、尤其是学生群体用的主要是有三种。
2253 1
重新更新VScode配置(C/C++)——负责任、手把手教学,亲测有效
|
Web App开发 自然语言处理 API
5000字详说Elasticsearch入门(一)
本文主要介绍快速入门Elasticsearch,从安装、基本概念、分词器、文档基本操作这4个方面快速入门。本篇是ES入门系列的第一篇,后续还有springboot项目集成ES、ES高级查询用法、数据库同步到ES的方案等。
5000字详说Elasticsearch入门(一)

热门文章

最新文章