求解一道疑似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

相关推荐

我已成为0offer的糕手:别惯着,胆子都是练出来的,这里认怂了,那以后被裁应届被拖工资还敢抗争?
点赞 评论 收藏
分享
求个公司要我:接好运
点赞 评论 收藏
分享
评论
点赞
1
分享
牛客网
牛客企业服务