如何求解以最大no为极限的棒材切割problem。允许的削减？
如何求解以最大no为极限的棒材切割problem。允许的削减？
提问于 2017-05-24 05:11:40
我知道如何用动态规划来解决棒材切割问题。但是，当我们限制允许的最大切数时，动态规划不能给出正确的answer.Even，我想不出这个问题的递归解决方案。帮助。
问题是，
通过砍掉棒子和出售零件来确定能获得的最大收益。
给定一根长度为N的杆，价格表P(i)对于长度为i.You的杆，在给定的杆上可作不超过K的切割。
示例：
N=10
K=3
\x{e76f} p(1) =1\x{e76f} p(2) =5\x{e76f} p(3) =8\x{e76f} p(4) =9\x{e}p(5)=10\x{e 010} p(6) = 22 \x{e} p(7) = 17 \x{e76f} p(8) = 20 x= p(9) = 24 x= p(10) = 30 x
最大可获得的收益是31通过切割成2段(总no =1，小于K=3)的长度6和4。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-05-24 14:50:33
我们可以通过增加一个二维，即到目前为止的割集数来扩展动态规划解。
D[n][k]是长度为n的杆使用精确的k裁剪的最大收入，可以定义如下：
D[n][k] = max(price[i] + D[n-i-1][k-1]) for all i in {1, 2, ..., n}由于我们最多希望削减K，而不是确切地说，最大的收入将是：
maxRevenue(N) = max(D[N][k]) for all k in {1, 2, ..., k}这将是O(N²K)，因为我们需要遍历所有的k (与典型问题的O(N²)相比)。
(Java)代码：
int[] price = {1, 5, 8, 9, 10, 22, 17, 20, 24, 30};
int N = price.length;
int K = 3;
int[][] D = new int[N+1][K+1];
for (int n = 1; n <= N; n++)
D[n][0] = price[n-1];
for (int k = 1; k <= K; k++)
for (int n = 0; n <= N; n++)
for (int i = 0; i <= n-1; i++)
D[n][k] = Math.max(D[n][k], price[i] + D[n-i-1][k-1]);
int best = 0;
for (int k = 0; k <= K; k++)
best = Math.max(best, D[N][k]);
System.out.println(best);现场演示。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44149463
复制相关文章
相似问题
腾讯云开发者
