我搜索了所有网站 . 但背包问题总是与权重和 Value 观有关 .
我必须为以下问题编写算法和C实现..
问题：
背包问题是给定一组正整数（a1，.....，an）和大小为s的背包，找到（a1，.....，an）的子集A，使得元素之和在A中最大但最多是s .
必须使用动态编程来设计算法 . 还必须证明正确性并且必须为此计算计算时间 .
你能为此提供任何有用的资源吗？任何人都可以解释如何做到这一点？因为在整个网络中我只能找到重量和值的背包问题 .
这个问题有点特殊 .
请尽快发布....
这是subset sum problem，它是背包的私有实例，其中 cost[i] = weight[i] 为每个项目 i .
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.
x<=S
D(x,n) = true
1 回答
这是subset sum problem，它是背包的私有实例，其中
cost[i] = weight[i]为每个项目i.DP解决方案遵循以下递归公式：
最后，
x<=S的最高值D(x,n) = true是最高可能值，最多为S.