n,m=map(int,input().split())
W=[]
V=[]
#转化为01背包问题,同时减少重复的数据,降低时间复杂度
for i in range(n):
a,b,c=map(int,input().split())
q=min(m//a,c)
p=1
while q>p:
W.append(a*p)
V.append(b*p)
q-=p
p*=2
W.append(a*q)
V.append(b*q)
#同01背包解法
n=len(W)
dp=[0]*(m+1)
for i in range(n):
for j in range(m,W[i]-1,-1):
dp[j]=max(dp[j],dp[j-W[i]]+V[i])
print(dp[m])
0.0分
0 人评分
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:541 |
A+B for Input-Output Practice (C++代码)浏览:609 |
回文数(一) (C语言代码)浏览:753 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:485 |
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1358 |
【魔板】 (C++代码)(时间超限,希望会的帮我改正一下)浏览:743 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:542 |
完数 (C语言代码)浏览:693 |
1035 题解浏览:785 |
模拟计算器 (C语言代码)浏览:2300 |