全部评论
个人思路: 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]即为答案。 不对请大佬轻喷。
楼上思路正解,相当于一个数组找出和为0的最长子序列,进一步可以优化成一维数组
相关推荐
10-30 17:07
University of California Riverside UE4 点赞 评论 收藏
分享