0-1背包问题

N,C=[int(each) for each in input().split()]
data=[]
for i in range(N):
    data.append([int(a) for a in input().split()])

################# 0-1 背包##################
dp=[[0 for j in range(C+1)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,C+1):
        if j <data[i-1][0]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-data[i-1][0]]+data[i-1][1])
x=[0]*N
k=N
while k>=1:
    l=C
    while l>=1:
        if dp[k][l]==dp[k-1][l]:
            x[k-1]=0
        else:
            x[k-1]=1
            l=l-data[k-1][0]
        k=k-1

可能存在问题,可以通过简单的测试用例

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每周一总结(4) 分布式ID 学习笔记

    趋势递增:分布式ID用来标识数据的唯一性,往往会被用作主键或者是唯一索引。常用的MySQL InnoDB,使用的索引往往是BTree索引,自增的数据在插入时会有...

  • Effective Java 第二版 学习笔记(2) 创建和销毁对象-多个构造器参数时考虑构建器

    重叠构造器模式可行,但是当有许多参数时,客户端代码会很难编写,并且难以阅读。也可以用JavaBeans莫斯。这种模式中,调用一个无参构造器来创建对象,然后调用s...

  • Java核心技术卷2 高级特性 学习笔记(5)

    为了获得最大的安全性,无论是加载类的默认机制,还是自定义的类加载器,都需要与负责控制代码运行的安全管理器类协同工作。

  • Python批量提取指定的站点空气质量数据

    对于我们下载的多数数据集,我们可能需要提取其中指定的来使用,比如这个空气质量数据集,全国那么多站点,我只想要我研究的区域的站点数据,然而,当我打开文件夹的时候,...

    郭好奇同学
  • 使用Python批量提取指定的站点空气质量数据

    对于我们下载的多数数据集,我们可能需要提取其中指定的来使用,比如这个空气质量数据集,全国那么多站点,我只想要我研究的区域的站点数据,然而,当我打开文件夹的时候,...

    bugsuse
  • 一文彻底搞懂BP算法:原理推导+数据演示+项目实战(下篇)

    鸢尾花数据集如图2所示,总共有三个品种的鸢尾花(setosa、versicolor和virginica),每个类别50条样本数据,每个样本有四个特征(花萼长度、...

    磐创AI
  • Lagrange、Newton、分段插值法及Python实现

    数据分析中,经常需要根据已知的函数点进行数据、模型的处理和分析,而通常情况下现有的数据是极少的,不足以支撑分析的进行,这里就需要使用差值法模拟新的数值来满足需求...

    统计学家
  • Vue移动端框架Mint UI教程-数据渲染到页面(六)

    拿到res.data之后,要赋值给page实例里面的data 所以在data里面设置一个默认的空数组

    王小婷
  • 数据科学家常遇到的10个错误

    数据科学家是“在统计方面比任何软件工程师都要出色,在软件工程方面比任何统计学家都出色的人”。许多数据科学家都有统计学背景,但很少有软件工程经验。我是一位高级数据...

    磐创AI
  • 数据科学家常犯的十大编程错误

    数据科学家是“比任何软件工程师都更擅长统计,比任何软件工程师都更擅长软件工程的的统计学家”。许多数据科学家都有统计学背景却缺乏在软件工程方面的经验。我是资深的数...

    AiTechYun

扫码关注云+社区

领取腾讯云代金券