Very good problem to learn knapsack (complete knapsack in this case).
My brutal-force solution in Python got AC too, which surprised me a bit. Here is the ideal DP solution. Just check comments:
T = int(input()) for _ in range(0, T): n, k = map(int, input().strip().split()) arr = [int(i) for i in input().strip().split()] dp = [0] * (k + 1) arr.sort() for g in range(1, k + 1): # k slots in knapsack for i in range(0, n): # for each candidate if arr[i] <= g: # each item, cost == gain dp[g] = max(dp[g], arr[i] + dp[g - arr[i]]) print (dp[k])
原文：http://www.cnblogs.com/tonix/p/4349273.html