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

技术标签： 算法  C语言  c语言  算法思想  

对上次的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;
}

测试用例
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Xminyang/article/details/52782201

智能推荐

KNN的简单Python实现以及kd树的建立与搜索_knn　kd tree python-程序员宅基地

文章浏览阅读1.1k次，点赞3次，收藏9次。KNN的简单Python实现以及kd树的建立与搜索KNN简介KNN算法实现kd树构建kd树查找引用KNN简介通过引入如下的一个问题来进行KNN算法的阐释，如图有三种不同颜色的豆子，我们如何判定未知的三种颜色属于哪一类呢？我们可以这样想这个问题，未知的种类的豆子离哪一类豆子的距离最近，就确定它为此种豆子。在介绍k近邻算法之前，我们首先介绍最近邻算法，最近邻算法的定义如下：为了判断一个未知样..._knn　kd tree python

求助！！！MFC基于对话框中IDC未定义的问题_c++ #define idc_button_opencom 1003-程序员宅基地

文章浏览阅读2.3k次。我有添加#include"Resource.h"为啥还一直提示未定义啊有大佬帮帮我吗????_c++ #define idc_button_opencom 1003

C语言基础：运算符（算术 / 关系 / 逻辑 / 位 / 赋值 / 杂项运算符）、运算符的优先级_按位与且赋值运算-程序员宅基地

文章浏览阅读1.9k次。运算符（算术 / 关系 / 逻辑 / 位 / 赋值 / 杂项运算符）、运算符的优先级_按位与且赋值运算

httpd的介绍-程序员宅基地

文章浏览阅读4.3k次，点赞2次，收藏10次。1.事先创建进程，并且适量维持适量的进程2.模块较小，核心较小，各种功能通过模块添加或者运行时也可配置3.支持单独编译模块，使用时添加4.支持多种虚拟主机配置（一个主机部署多个网站）如ip，端口和域名5.支持https协议（证书加密）6.用户认证7.限制所有的ip和域名访问8.目录的访问控制，用户访问某特定目录时需要提供用户名和密码，访问默认不需要9.支持URL重写10.多处理模块1.支持动态共享对象模块的装/卸载机制（装载，功能启用，卸载功能关闭）2.支持事件驱动（event mpm）,电脑点一个文件，C_httpd

实战经验 | STM32H5_DA之初体验（带TrustZone）_provisioning、irot provisionned、tz-close-程序员宅基地

文章浏览阅读1k次，点赞26次，收藏25次。如上图所示，继续在 TPC 工具中，在 Permission Mask 下，激活允许的操作许可，被激活的就是 DA 认证通过后，允许的操作. 然后在 Output File 处选择输出文件。如上图所示，在接下来的界面中，在 Key File Path 处选择之前生成的私钥文件 key_1_root.pem：C:\workspace\STM32Cube_FW_H5_V1.1.0\Projects\NUCLEO-H563ZI\ROT_Provisioning\DA\Keys\key_1_root.pe。_provisioning、irot provisionned、tz-close

tf.contrib.graph_editor.graph_replace-程序员宅基地

文章浏览阅读591次。摘自:https://tensorflow.google.cn/versions/r1.15/api_docs/python/tf/contrib/graph_editor/graph_replace创建一个新的图graph用于计算replaced tensor的目标值tf.contrib.graph_editor.graph_replace( target_ts, repl..._tf.contrib.graph_editor.graph_replace

随便推点

学习go语言国内最全资料链接_七米 golang-程序员宅基地

文章浏览阅读571次，点赞5次，收藏4次。就最近和各位大佬认识下来，以前觉得学习go语言，可能资料比较少，可是后来才发现，原来资料并不少，甚至可以说通过大家的努力，go社区已经非常包容且完善了接下来会推荐一些资料，以及大佬社区微软go语言中文网Gopher China golang中国LearnKu自建博客：boyacch码农桃花源七月天面向信仰编程less is betterPure White煎鱼mzh鸟窝峰云就她了luozhiyun`s BlogVincent Blanchon地鼠导航go夜读g_七米 golang

linux+tar怎样解压zip文件内容,linux tar压缩解压文件-程序员宅基地

文章浏览阅读1.7w次。时间：2016-08-30作者：admin 阅读:次-c: 建立压缩档案-x：解压-t：查看内容-r：向压缩归档文件末尾追加文件-u：更新原压缩包中的文件这五个是独立的命令，压缩解压都要用到其中一个，可以和别的命令连用但只能用其中一个。下面的参数是根据需要在压缩或解压档案时可选的。下面的参数-f 是必须的-f: 使用档案名字，切记，这个参数是最后一个参数，后面只能接档案名。# tar -cf..._tar怎么解压zip文件

一名双非程序媛面试蚂蚁、美团、携程等大厂拿 offer 分享面试过程_双非女后端大厂面经-程序员宅基地

文章浏览阅读184次。今天小编给大家带来一个优秀妹子的后台面试经验总结，希望对正在面试或者以后需要面试的人提供一些参考和帮助。具体如下：本人妹子，985 硕士，211 本科，专业都是软件工程，一直投的是 Java 后台开发，只投过一次网易的测试，技术不是大牛，但是比较努力。实验室没有项目，so 项目经验是 0，在去年这个时候看到实验室师兄找工作的艰难，因此开始复习的时间比较早。最开始先看的 java 基础，看的马某某的视频，后面就看框架视频，后来也看过某某学院的视频，都是在网上找的免费的。..._双非女后端大厂面经

运行成功：char转换为wchar_t的代码_char 转换成 wchar_t-程序员宅基地

文章浏览阅读593次。　　具体代码是：int charTowchar(char* pSrc, wchar_t* pDest){ if (pSrc == NULL || pDest == NULL) { return 0; } setlocale(LC_CTYPE, "zh_CN.utf8"); int w_size = mbstowcs(NULL, pSrc, 0) + 1; //w_size=0说明出错了。可能有非法字符，也可能是locale设置不对。_char 转换成 wchar_t

Spring Security最难的地方就是这个了-程序员宅基地

文章浏览阅读3.6k次，点赞6次，收藏6次。本篇摘自胖哥最新的基于Spring Security 5.6.x的《Spring Security干货》教程。旧版的教程将在2022年1月1日下线，请需要的同学尽快通过本公众号回复“202..._configurer.addobjectpostprocessor

java身份证号码正则表达式校验（亲测可用） Java正则校验手机号_java校验身份证号的正则表达式-程序员宅基地

文章浏览阅读1w次，点赞3次，收藏6次。// 原文：https://blog.csdn.net/u011106915/article/details/76066985public class IDUtils { public static boolean isIDNumber(String IDNumber) { if (IDNumber == null || "".equals(IDNumber)) { return false; } // 定义判别用户身份证号的..._java校验身份证号的正则表达式

推荐文章

热门文章

相关标签