拼接木材
现在有一批长度不同的木材woods，现在需要将木材进行拼接，正好达到总长度length,在不考虑切割木材，并且每种长度的木材不限量供应情况下，返回满足要求的最少木材数量，如果无法通过组合达到规定长度，则返回-1。
输入描述
木材长度列表和需要达到的总长度length
木材种类：1 <= len(woods) <= 100
木材长度：1 <= woods[i] <=1000
品长及：1 <= length <=10000
输入的2行信息均以字符串形式输入，需要自己转换为列表和整数
输出描述
返回满足要求的最少木材数量，如果无法通过组合达到规定长度，则返回-1
样例
输入
[1, 2, 3, 5]
9
输出
3
思路
这道题其实就是一个完全背包问题
| 拼接木材 | 完全背包 |
|---|---|
| 木材 | 物品 |
| 长度length | 背包容量 |
| 木材长度 | 物品体积 |
| 木材数量 | 物品价值 |
| 木材数量最小 | 物品价值最大 |
这道题可以说成这样一个背包问题
有n种物品，第i种物品的体积是\(v_i\)，每一种物品都有无限个，背包容量为v，所有物品的价值都是1，问：如果把背包恰好装满，最小能装多少价值？如果无法恰好装满，请输出-1
状态转移方程
\[\left( i,v\right) = min\begin{cases}\left( i-1,v\right) \\ \left( i,v-v_{i}\right) + 1\end{cases} \]其中\((i, v)\)表示考虑前i种物品，恰好可以装满容量为v的背包，能装的最小价值
也就是考虑前i种木材时，恰好可以拼接为长度为v，所需要的最少的木材
woods = [0] + eval(input())
length = int(input())
n = len(woods) - 1
dp = [0.0] + [float('inf')] * length
for i in range(1, n + 1):
for j in range(1, length + 1):
if woods[i] <= j:
dp[j] = min(dp[j], dp[j - woods[i]] + 1)
res = dp[length] if dp[length] != float('inf') else -1
res = int(res)
print(res)