一维套料

admin1

[code](defun c:test(/ lst maxlen)
(setq lst '(144 35 23 86 99 12 230 12 12 14 132 189 6 3 99))
(setq maxlen 240.0)
(get_cutlist lst maxlen)
)
;;  result ((99) (99 132) (86 144) (12 12 12 14 23 35 189) (3 6 230))

;;  CAB 03-10-06
(defun get_cutlist (lst maxlen / cutlst itm lst ptr tl x finallst remove-at)
(defun remove-at (lst pos / head) ; Tony Tanzillo
   (repeat pos
     (setq head (cons (car lst) head)
           lst  (cdr lst)
     )
   )
   (append (reverse head) (cdr lst))
)

(setq lst (mapcar '(lambda (x) (nth x lst)) (vl-sort-i lst '>)))
;;  step through lst
(while lst
   (setq cutlst (list (car lst)) ; start new cutlist w/ first item
         lst    (cdr lst) ; remove first item
         ptr    (1- (length lst)) ; point to end of list
         tl     (apply '+ cutlst) ; total length so far
   )

   ;; build the cutlst
   (while (and lst cutlst)
     ;; find largest next cut
     ;; exit conditions ptr < 0 or itm length exceeds max
     (while (and (< (+ tl (setq itm (nth ptr lst))) maxlen)
                 (> ptr 0))
       (setq ptr (1- ptr))
     )

     (if (> ptr -1)
       (if (= ptr (1- (length lst)))
         ;;  no more cuts fit, go to next
         (setq finallst (cons cutlst finallst)
               cutlst   nil
         )
         (setq cutlst (cons (nth (1+ ptr) lst) cutlst)
               lst    (remove-at lst (1+ ptr))
               tl     (apply '+ cutlst) ; new total

         )
       )
       ;; else exausted pointer
       (setq finallst (cons cutlst finallst)
             cutlst   nil
       )
     )
   )
)
(if cutlst
   (cons cutlst finallst)
   finallst
)
)[/code]

jxmjg

“一维套算法”这个术语并不是一个标准的算法名称，它可能是在描述一类特定问题求解策略时所用的非正式表述。不过，从字面上理解，“一维套”可能指的是在一维空间或一维数据结构（如数组）上应用某种嵌套或迭代的算法思想。这里，我将基于一维数据结构（如数组）上的常见算法思想，给出一个可能的解释，即“一维套娃”算法思想在解决最长上升子序列（Longest Increasing Subsequence, LIS）问题上的应用。
最长上升子序列（LIS）问题
最长上升子序列问题是动态规划中的一个经典问题。给定一个无序的整数数组，要求找到数组中最长的上升子序列的长度。一个上升子序列是指原数组的一个子序列，其中任意两个相邻的元素都满足后一个元素大于前一个元素。
算法思想
在解决LIS问题时，可以采用动态规划的思想。我们定义一个数组dp，其中dp[i]表示以nums[i]结尾的最长上升子序列的长度。对于数组中的每个元素nums[i]，我们遍历它之前的所有元素nums[j]（其中j < i），如果nums[j] < nums[i]，则说明nums[i]可以接在nums[j]后面形成一个更长的上升子序列。因此，我们更新dp[i]为dp[j] + 1和dp[i]中的较大值。最后，遍历dp数组找到其中的最大值，即为所求的最长上升子序列的长度。
算法步骤

初始化一个与输入数组nums等长的数组dp，所有元素初始值为1（因为每个元素至少可以单独构成一个长度为1的上升子序列）。
遍历数组nums，对于每个元素nums[i]，再遍历它之前的所有元素nums[j]（其中j < i）。
如果nums[j] < nums[i]，则更新dp[i] = max(dp[i], dp[j] + 1)。
遍历完所有元素后，找到dp数组中的最大值，即为最长上升子序列的长度。

示例
输入数组：[2, 6, 1, 9]

初始化dp = [1, 1, 1, 1]
遍历nums，更新dp：
对于nums[1] = 6，比较前面的nums[0] = 2，因为2 < 6，所以dp[1] = dp[0] + 1 = 2
对于nums[2] = 1，前面的元素都比它大，所以dp[2]保持为1
对于nums[3] = 9，比较前面的元素，dp[3]更新为dp[1] + 1 = 3（因为以6结尾的子序列最长为2，接上9后长度为3）


最终dp = [1, 2, 1, 3]，最长上升子序列的长度为3。

这就是一种在一维数据结构上应用“套娃”思想（即嵌套或迭代求解）的算法示例。不过请注意，“一维套算法”并不是标准术语，这里只是为了解释而构造的一个表述。