from collections import defaultdict for _ in range ( int ( input ())): m, x = map ( int , input (). split ()) c = [ 0 ] * (m + 1 ) h = [ 0 ] * (m + 1 ) for i in range (m): c[i], h[i] = map ( int , input (). split ()) mh = sum (h) dp = [ 0 ] + [ float ( 'inf' )] * mh for i in range (m): for j in range (mh, h[i] - 1 , - 1 ): if i * x >= dp[j - h[i]] + c[i]: dp[j] = min (dp[j], dp[j - h[i]] + c[i]) for i in range (mh, - 1 , - 1 ): if dp[i] != float ( 'inf' ): print (i) break link: https://codeforces.com/contest/1974/problem/E """ 1. 背包容量 capacity, n 件物品 2.n 件物品的重量 w, 价值 v """ def knapsack_01 ( items , capacity ): n = len ( items ) # dp[i][j] 代表 前 i 个物品 j 容量时的价值 dp = [[ 0 ] * ( capacity + 1 ) for _ in range (n + 1 )] for i in range ( 1 , n + 1 ): weight, val = items [i - 1 ] for j in range ( capacit...
评论
发表评论