python部分背包问题 贪心算法

Question

给出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

Answer 1

你题目的解答代码如下：

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)))

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

Answer 2

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632