贪心算法-背包问题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

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

智能推荐

自动曝光技术—亮度获取_相机目标亮度是什么-程序员宅基地

文章浏览阅读1k次。1、介绍自动曝光技术可以分成三步骤，分别是亮度获取、亮度分析和曝光调节。这一章内容主要介绍一下自动曝光技术中的亮度获取方法。2、自动曝光技术主要分为光学_相机目标亮度是什么

Centos 7 一键安装Redash （Centos7 + Docker）_centos7 redash 安装-程序员宅基地

文章浏览阅读488次。详情请参照下方博客：博客地址本人亲测有效，不需要安装其他程序，复制好脚本，直接执行即可_centos7 redash 安装

【Python】科研代码学习：十 evaluate (metrics，Evaluator)_python evaluate-程序员宅基地

文章浏览阅读1k次，点赞21次，收藏15次。【代码】【Python】科研代码学习：十 evaluate (metrics，Evaluator)_python evaluate

Tcp如何解决丢包和乱序的问题_tcp乱序的解决办法-程序员宅基地

文章浏览阅读1.3k次。于是接收方一共收到3个ack=3，于是马上重发3号数据包，然后接收方接收到了3号数据包，此时由于4,5号数据包也已经被接收了，所以发送ack=6，表示接下来希望接收序号为6的数据包。但是3由于某些原因丢失了，没发到接收方那里，4到达了，于是接收方继续发送一个ack=3。1,2先到了，于是接收方返回一个ack=3，表示接下来想要接受一个序号为3的数据包。然后5又到达了，接收方继续发送一个ack=3。发送方发送1，2,3,4,5 一共五份数据。_tcp乱序的解决办法

升级鸿蒙系统无法连接服务器,升级到鸿蒙系统后经常提示当前无网络，请检查后重试的说明...-程序员宅基地

文章浏览阅读2.4w次。问题：自从升级到了鸿蒙系统之后，在看抖音时经常会出现提示“当前无网络，请检查后重试”，WIFI已经确认过了，无任何问题，该如何处理？问题追加：要么出现如下图提示：要么出现如下图提示：网络不一样，但都是提示“当前无网络，请检查后重试”。回答：建议尝试还原下网络，有用户重置还原网络设置改善了好多，另外，请把系统更新至新版。注：有不少用户也有此情况，以下是他们的反馈：1、可能是跟鸿蒙系统本身有关，因为原..._鸿蒙系统状态网络不可用

Qt：Qt框架的初步认识和基本使用

QT框架基本认识

随便推点

C语言函数指针数组_c语言定义函数指针数组-程序员宅基地

C语言函数指针数组的使用方法非常重要，它可以存储多个函数指针，实现灵活的函数调用。通过函数指针数组，我们可以在运行时根据需求选择调用不同的函数。这种技术在编写大型程序时尤为有用。

【并查集】个人心得&&kuangbin带你飞并查集专题全题解_nefu_qky并查集-程序员宅基地

文章浏览阅读3.1k次，点赞19次，收藏40次。题目链接：普通并查集：1、2、3文章目录1.Wireless Network POJ - 22362.The Suspects POJ - 16113.How Many Tables HDU - 12131.Wireless Network POJ - 2236将所有可以互相连通的电脑放在一个集合中对于O操作（修电脑），将该电脑与所有已经修好的电脑判断一下，若距离小于D，则合并集合对于S操作（查询），直接查询两个电脑是否属于同一个集合即可#include <iostream>#i_nefu_qky并查集