贪心算法-背包问题2_计算背包问题的贪心算法,同时得到解向量,运行时,应该输入什么-程序员宅基地

对上次的C语言代码做了一些修改，可以打印出装进背包里面的物品的顺序编号。

// 贪心算法-背包问题-解向量.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <algorithm>
using namespace std;
#define N 3

int flag = 0;//装进物品的总数标记

typedef struct
{
    int w;//重量
    int v;//价值
    double c; //性价比
    int index;
}bag;
bool cmp(bag a, bag b)
{
    return a.c > b.c;
}
double GreedyKnapsack(bag a[], int n, double weight)
{ //返回最大价值
    double c_left = weight;  //背包的剩余容量
    int i = 0;
    double b = 0; //获得的价值
    while (i < n&&a[i].w < c_left)
    { //能够放下整个的物品时
        c_left = c_left - a[i].w;
        b = b + a[i].v;
        ++i;
        ++flag;
    }
    if (i < n)
    {
   //只能放下物品的一部分时
        b = b + a[i].v*(c_left / a[i].w);
        ++flag;
    }
    return b;
}
int main()
{
    int sum_weight;
    double value;  // 书包所能容纳的最大价值
    printf("请输入书包的负重：");
    scanf_s("%d", &sum_weight);

    bag bags[N];
    printf("请依次输入%d种物品的重量和价值:\n", N);
    for (int i = 0; i < N; i++)
    {
        printf("物品%d\t", i);
        scanf_s("%d", &bags[i].w);
        scanf_s("%d", &bags[i].v);
        bags[i].index = i;
        bags[i].c = (bags[i].v*1.0) / bags[i].w;
    }
    sort(bags, bags + N, cmp);
    value = GreedyKnapsack(bags, N, sum_weight);
    printf("该书包所能容纳的最大价值是：%.2f\n", value);
    printf("装进书包里的物品顺序是：");
    for (int i = 0; i < flag; i++)
        printf("%d", bags[i].index);
    printf("\n\n");
    return 0;
}

测试用例

本文链接：https://blog.csdn.net/Xminyang/article/details/52782201

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

python delphi通信_python + delphi dll 混合编程-程序员宅基地

文章浏览阅读304次。本文为作者原创作品，转载请注明出处。作者：汉学实践中需要在 python 中生成报表，开始尝试使用 PIL 库向空报表图片中插入所需的文字，可是后插入的文字与原有文字不太和谐，后来想到可以使用 delphi 开发 DLL，在DLL中实现报表生成，并由 python 调用 DLL，实践结果如下：一、用 delphi 开发 DLLlibraryfr;usesSysUtils,Classes,frxCl..._delphi python 发布dll

阿里-paraformer论文详解_paraformer模型-程序员宅基地

文章浏览阅读167次。转发：https://zhuanlan.zhihu.com/p/547497094论文：https://link.zhihu.com/?背景：近年来，随着端到端语音识别的流行，基于 Transformer 结构的语音识别系统逐渐成为了主流。然而，由于 Transformer 是一种自回归模型，需要逐个生成目标文字，计算复杂度随着目标文字数量而呈线性增加，限制了其在工业生产中的应用。_paraformer模型

View的事件体系（一）view基础和view的几种滑动方式_viewvelocity.view方法-程序员宅基地

文章浏览阅读251次。View的事件体系一_viewvelocity.view方法

linux命令打错了怎么办,如何快速纠正错误的linux命令?-程序员宅基地

文章浏览阅读4.7k次，点赞3次，收藏18次。如何快速纠正你的linux命令?我们在输入命令的时候，难免会出现输入命令错误，或者输入过多，过少的情况，那么除了各种按方向键退回之外，还有什么快速纠正命令的方法?本文用|表示光标位置。移动到命令开头举个例子，你准备执行一个命令：./test-axxx-bbbb|但是你输入的时候，少了前面的./(为什么执行程序的时候前面要加./)test-axxx-bbbb这个时候你一般会怎么办?使用方向键将光标移..._linux命令输错了,咋移回去

IDEA+Java+SSM+Mysql+Bootstrap实现Web学生信息管理系统_学生管理系统ssmidea-程序员宅基地

文章浏览阅读8.8k次，点赞12次，收藏170次。目录一、系统介绍1.开发环境2.技术选型3.系统功能二、系统展示1.登录系统2.管理员-首页3.管理员-学生管理4.管理员-课程管理5.管理员-班级管理6.管理员-更改密码7.用户-首页8.用户-查看课表9.用户-选课三、部分代码ClassesControllerCourseControllerStudentControllerTeacherControllerUserController四、其他1_学生管理系统ssmidea

win10安装Ubuntu报错Error code: Wsl/Service/0x8007273d-程序员宅基地

文章浏览阅读4.9k次，点赞6次，收藏7次。下载完成后，启动安装报错，错误代码为0x8007273d。_error code: wsl/service/0x8007273d

随便推点

log4cplus在VS项目中的使用-程序员宅基地

文章浏览阅读593次。log4cplus是C++编写的开源的日志系统，宣称具有线程安全、灵活、以及多粒度控制的特点，通过将日志划分优先级使其可以面向程序调试、运行、测试、和维护等全生命周期。你可以选择将日志输出到屏幕、文件、甚至是远程服务器；通过指定策略对日志进行定期备份等等（该段为引用其他文章）。1.编译log4cplus库在网上下载log4cplus库（我下载了 log4cplus-1.2.1.zip），..._log4cplus-1.2.1.zip

sql中的模糊匹配与正则表达式_sql 模糊匹配-程序员宅基地

文章浏览阅读2.4k次。sql中的模糊匹配与正则表达式_sql 模糊匹配

Shp格式详解与在线打开、查看-程序员宅基地

文章浏览阅读7.6k次，点赞33次，收藏36次。使用3D模型在线转换网站进行shp格式在线打开、查看和转换，NSDT 3dconvert支持将shp格式在线转换为glb、gltf、obj、stl、dae、ply、off等格式。_shp

Unity2017 Timeline实例解析:游戏场景中的动画_timeline自定义轨道 2017-程序员宅基地

文章浏览阅读4.2k次。转载注明出处：点击打开链接Unity 2017.1 推出的Timeline功能，不仅可以高效的帮助大家实现游戏场景中的物体动画，还可以制作出更为复杂的过场动画及电影内容。今天这篇文章将由Unity大中华区技术经理成亮，通过实例分析让大家了解Timeline的多轨道，把各类场景中的元素整合实现更为复杂的动画。Timeline简介Timeline 是一套基于时间轴的多轨道动画系统，_timeline自定义轨道 2017

【经典算法题】零钱兑换_java 兑换零钱算法-程序员宅基地

文章浏览阅读2.4k次。【经典算法题】零钱兑换Leetcode 0322 零钱兑换题目描述：Leetcode 0322 零钱兑换分析本题的考点：背包问题。完全背包问题，amout为容量；物品体积为coins[i]，价值为1。本题和Leetcode 0279 完全平方数十分类似，可以参考LC279的分析。注意本题和Leetcode 0518 零钱兑换 II的区别，LC518让求得是体积恰好是m的方案数，本题求的是体积恰好是m需要用的最少硬币数。代码C++class Solut_java 兑换零钱算法

精心整理史上最全的数据结构flash演示动画，共5个版本，祝大家考研成功！_数据结构 flash-程序员宅基地

文章浏览阅读1.8k次，点赞2次，收藏4次。精心整理史上最全的数据结构flash演示动画，共5个版本，祝大家考研成功！\数据结构flash演示\版本1\数据结构flash演示\版本2\数据结构flash演示\版本3\数据结构flash演示\版本4\数据结构flash演示\版本5\数据结构flash演示\版本1\1-4 算法和算法分析冒泡排序.swf\数据结构flash演示\版本1\10-1-1插入排序.swf\数据结构fl..._数据结构 flash