使用动态规划的 Value 无关背包问题

我搜索了所有网站 . 但背包问题总是与权重和 Value 观有关 .

我必须为以下问题编写算法和C实现..

问题:

背包问题是给定一组正整数(a1,.....,an)和大小为s的背包,找到(a1,.....,an)的子集A,使得元素之和在A中最大但最多是s .

必须使用动态编程来设计算法 . 还必须证明正确性并且必须为此计算计算时间 .

你能为此提供任何有用的资源吗?任何人都可以解释如何做到这一点?因为在整个网络中我只能找到重量和值的背包问题 .

这个问题有点特殊 .

请尽快发布....

回答(1)

3 years ago

这是subset sum problem,它是背包的私有实例,其中 cost[i] = weight[i] 为每个项目 i .

DP解决方案遵循以下递归公式:

D(0,i) = true
D(x,i) = false        x < 0
D(x,0) = false        x > 0
D(x,i) = D(x-arr[i],i-1) OR D(x,i-1)

最后, x<=S 的最高值 D(x,n) = true 是最高可能值,最多为S.