请问python的最佳填充算法应该怎么写？

netspirit

假设现在有几千的个数据集。每个数据集里面包含几个到几百个数据。
然后我需要把这些数据集放到一些列表里面。
要求每个列表里面的总数据不能超过999个
而且数据集不能拆分
而且列表尽可能的少
如何实现这个算法？


举个例子，比如有以下几个数据集，里面的数据量为920,670,70,320
然后我要把他们放在尽可能少的列表中，每个数据集不拆分
最佳的方法是[920,70],[670,320]
如果不智能的话就会出现[990],[670,70],[320]
但是这是一个很简单的情况下
假设总共有几千个数据集，那如何把这些数据集放在多个列表中，并保证列表数量最少？

感谢大家～～～～～～

wkdxz

我感觉可以试试numpy

[Python] 纯文本查看 复制代码

import numpy as np
ls = np.array(range(30))

print('原始列表',ls)
new_ls = np.reshape(ls,(2,15))

print('新列表',new_ls)

.reshape后面，单个列表的长度，可以先判断一下长度，再决定

dd511990

这应该就是“背包问题”，一般总是用来演示“遗传算法”……但实际效果都不咋样

pzx521521

不一定是最佳的
说下思路:
数据集按数据量(长度)排序
然后左右两个游标
一个一个判断, 如果满了就找下一个:

[Golang] 纯文本查看 复制代码

package main

import (
	"fmt"
	"sort"
)

func main() {
	capacity := 999
	arr := []int{920, 670, 70, 320}
	length := len(arr)
	sort.Ints(arr)
	left := 0
	right := length - 1
	for left < right {
		if arr[right]+arr[left] <= capacity {
			length--
			right--
		}
		left++
	}
	fmt.Printf("%v\n", length)
}

[Python] 纯文本查看 复制代码

capacity = 999
arr = [920, 670, 70, 320]
length = len(arr)
arr.sort()
left = 0
right = length - 1
while left < right:
    if arr[right]+arr[left] <= capacity:
        length-=1
        right-=1
    left+=1
print(length)

yep96

感觉可以01背包先尽可能的用长的填满整个列表
然后再删除已经填充的，继续做直到填完
因为已经有999这个长度在这里，实现起来不会很难

可能不会是最优，但应该差距不大

chr_233

先把数据集按元素个数排序，每次取最大的，然后剩余空间范围内再取尽可能大的，直到塞不下新的数据集，然后再开一个新列表，重复。