棒材切割问题
给出一根长度为n英寸的杆和包含小于n的所有尺寸的价格的价格清单。通过切割杆并出售这些杆来确定可得的最大值。例如，如果杆长为8，并给出了不同部件的值如下，则最大可得值为22 (通过切割两块长度2和6)。
length | 1 2 3 4 5 6 7 8
-------------------------------------------
price | 1 5 8 9 10 17 17 20如果价格如下，则最大可得值为24 (通过切割8条长度1)。
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 3 5 8 9 10 17 17 20输入将以这种形式给出:价格将按升序排列，指数从1到n由空格隔开。
{price of length 1} {price of length 2}.... {price of length N}
输出应是可获得的最大值。
{maxVal}
Python中的一种非高尔夫解决方案是：
INT_MIN = -32767
def cutRod(price, n):
val = [0 for x in range(n+1)]
val[0] = 0
for i in range(1, n+1):
max_val = INT_MIN
for j in range(i):
max_val = max(max_val, price[j] + val[i-j-1])
val[i] = max_val
return val[n]
arr = [1,2,3,4,5,6,7,8,9,10]
size = len(arr)
print(cutRod(arr, size))测试用例：
| Input | Output |
|:------------------------------------------------------------------------------:|:------:|
| `1 5 8 9 10 17 17 20` | `22` |
| `1 3 2 5 6 7 4 8` | `12` |
| `5 6 3 2 4 6 8 7 3 4 6 2 12 4 5 7 4 3` | `90` |
| `23 2 3 45 34 23 3143 13 13 213 1321 3123 12 312 312 31 3 213 432 41 3 123 43` | `9475` |回答 11
Code Golf用户
发布于 2021-02-04 01:34:48
Code Golf用户
发布于 2021-02-04 05:38:33
JavaScript (Node.js)，57字节
a=>a.map((v,i)=>a[i]=w=a.map(u=>v=(u+=a[--i])>v?u:v)|v)|w因为问题是背包问题。设val\left[i\right] 为长度i段的价格。我们有：
dp\left[len\right]就是答案。
为了获得更多的字节，我们将转换方程稍微修改为dp\left[i\right] = \max\left\{val\left[i\right], \max_{j=1..i-1} \left\{ dp\left[j\right] + dp\left[i-j\right] \right\} \right\} 。
在迭代期间，我们将a用于val和dp。当尝试计算a\left[i\right]时，所有值a\left[0..i-1\right]都等于dp，所有其他值都等于val。另外，我们的数组是0索引，而不是1索引.所以我们把方程修改成
使用这样的特性:当访问值超出数组范围时，将返回undefined。在undefined结果NaN上进行数学运算。NaN>v也将是false。我们可以忽略来自j=0..i-1的\max部件。代码如上所示。
Ungolfed程序作为参考：
int f(int* a) {
int i, j, val;
// before loop: a[i] = price of length (i+1) segement
// after loop: a[i] = max sum price of cutted length (i+1) segment
for (i = 0; a[i]; i++) {
// before loop j
// a[i] = price of length (i+1) segment
// = price if do not cut the segment
for (j = 0; j < i; j++) {
// price when cut the segment into two parts with length (j+1), (i-j)
val = a[j] + a[i - j - 1];
// we prefer higher price if we can
if (a[i] < val) {
a[i] = val;
}
} // j
} // i
return a[i - 1];
}以上C代码可能适用于81个字节，但仍然比JavaScript实现要长。:(
- -5字节多亏了阿纳尔德
Code Golf用户
发布于 2021-02-04 01:16:56
JavaScript (ES6)，78字节
由于@Davide保存了1个字节
a=>(m=F=(n,i=0,s=0)=>n?i>n||F(n+~i,i,s+a[i])|F(n,i+1,s):m=s<m?m:s)(a.length)&m评论
a => ( // a[] = input array
m = // initialize m to a non-numeric value
F = ( // F is a recursive function taking:
n, // n = integer to be partitioned
i = 0, // i = integer to be subtracted from n (-1)
s = 0 // s = price sum
) => //
n ? // if n is not equal to 0:
i > n // abort if i is greater than n
|| // otherwise:
F( // first recursive call with:
n + ~i, // n - i - 1
i, // i unchanged
s + a[i] // s + i-th price
) | //
F( // second recursive call with:
n, // n unchanged
i + 1, // i + 1
s // s unchanged
) //
: // else:
m = s < m ? m // update m to max(m, s)
: s //
)(a.length) // initial call to F with n = length of a[]
& m // return mhttps://codegolf.stackexchange.com/questions/218544
复制相似问题
腾讯云开发者
