lilili07 2022-03-30 15:42 采纳率: 72.7%
浏览 84
已结题

python部分背包问题 贪心算法

给出n个物体,第i个物体重量为w_i.选择尽量多的物体,使得总重量不超过C.其中参数n为正整数,w_i,C为正的有理数。

输入格式:
第一行输入n和C,用空格隔开。

第二行输入w_1, w_2 ...w_n.共n个数,用空格隔开。

输出格式:
第一行输出选择的物体数量。

第二行按从小到大的顺序输出选择的物体编号i。

注:如果物体数量相同有多种选择,请输出物体重量和最小的物体编号。
第一组测试用例是
5 10
4 2 3 1 5
输出
4
1 2 3 4
第二组是
5 10.1
4.2 1.9 3.1 1 5
输出
3
2 3 4

  • 写回答

2条回答 默认 最新

  • 关注

    你题目的解答代码如下:

    n,c = input().split()
    n = int(n)
    c = float(c)
    w = list(map(float,input().split()))
    li = sorted(enumerate(w,start=1), key=lambda x: x[1])
    res = []
    for i,v in li:
        if c-v<0:
            break
        c -= v
        res.append(i)
    res.sort()
    print(len(res))
    print(" ".join(map(str,res)))
    

    img

    如有帮助,请点击我的回答下方的【采纳该答案】按钮帮忙采纳下,谢谢!

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月8日
  • 已采纳回答 3月31日
  • 创建了问题 3月30日

悬赏问题

  • ¥15 BP神经网络控制倒立摆
  • ¥20 要这个数学建模编程的代码 并且能完整允许出来结果 完整的过程和数据的结果
  • ¥15 html5+css和javascript有人可以帮吗?图片要怎么插入代码里面啊
  • ¥30 Unity接入微信SDK 无法开启摄像头
  • ¥20 有偿 写代码 要用特定的软件anaconda 里的jvpyter 用python3写
  • ¥20 cad图纸,chx-3六轴码垛机器人
  • ¥15 移动摄像头专网需要解vlan
  • ¥20 access多表提取相同字段数据并合并
  • ¥20 基于MSP430f5529的MPU6050驱动,求出欧拉角
  • ¥20 Java-Oj-桌布的计算