求解一道疑似dp的算法题

思考了很久,求大佬们给个思路

#笔试题目#
全部评论
个人思路:     1.将每个Vi-K*Ci=Wi,问题等价于选择尽可能多的Wi加起来凑成0;     2.dp[i][c]表示前i件商品(W)凑成c最多可以选多少件;      3.dp[i][c] = max(dp[i-1][c], dp[i-1][c-Wi] + 1);     4.dp[N][0]即为答案。 不对请大佬轻喷。
点赞 回复 分享
发布于 2019-10-12 12:18
楼上思路正解,相当于一个数组找出和为0的最长子序列,进一步可以优化成一维数组
点赞 回复 分享
发布于 2019-10-12 12:37

相关推荐

不愿透露姓名的神秘牛友
10-05 10:13
已编辑
HHHHaos:让这些老登来现在秋招一下,简历都过不去
点赞 评论 收藏
分享
斑驳不同:还为啥暴躁 假的不骂你骂谁啊
点赞 评论 收藏
分享
评论
点赞
1
分享
牛客网
牛客企业服务