木材切割问题

发表于 | 分类于 |
字数统计: 847 | 阅读时长 ≈ 3

木材切割问题

一个木匠从木材公司买了一批木材，每块木材的长度均相同，但由于制作家具时所需的木块长度各不相同，因此需要把这些木材切割成长度不同的木块。同时每次切割时由于锯子本身有一定的宽度，因此每切割一次就会浪费掉一些木料。请设计一个程序使木匠能够用最少的木材切割出所需的木块。

输入描述：

输入有若干个测试样例，每个测试样例占一行。每行由若干个整数构成，第一个整数为所购买的木块的长度L$(0<L<=30000)$,第二个整数为锯子的宽度W$(0<W<=1000)$,其后的若干个整数分别表示制作家具时需要的木块的长度。

输出描述：

每个测试样例输出一行，为一个整数N，表示制作家具时需要购买的木块的数量。

样例输入：

1000 100 250 250 500 650 1000

1000 50 200 250 250 500 650 970

样例输出：

3

4

思路

这里先解决掉每次切割都会损耗锯子宽度的木材的问题。 给每个需要的木材加上锯子的宽度，然后给购买的木材的长度也加上一个木块的长度。这样就可以不考虑切割过程中锯子的损耗了。

然后就是贪心了，从木块中选择长度小于当前木料剩余长度的最大木块切割出去，如果没有一块小于当前木块了，那就用一块新的。消耗木材量加一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import bisect
n = int(input())

maxlen = int(input())
len_a = int(input())

lens = [0]*n

for i in range(n):
	lens[i] = int(input())
	lens[i] += len_a

maxlen += len_a

lens.sort()

print(lens)

left = maxlen
ans = 0
while len(lens):
	
	site = bisect.bisect(lens,left)
	
	if site == 0:
		ans += 1
		left = maxlen
		continue
		
	left -= lens[site-1]
	lens.pop(site-1)
	
if left != maxlen:
	ans+=1
		
	print(site,left,lens)
print(ans)

回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
int arr[105][105];
int L = 1000, W = 50;
// int len[105] = {200,250,250,500,650,970}, n = 6;
int len[105] = {970,650,500,250,250,200}, n = 6;
int mark[105];
int ans = 6;
void foo(int k)
{
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < n; j++)
            printf("%d%c", arr[i][j], j == n - 1 ? '\n' : ' ');
    }
    printf("------------\n");
}
void dfs(int row, int col, int remain)
{
    if (row == n)
        return;
    for (int i = 0; i < n; i++)
    {
        if (!mark[i])
            break;
        if (i == n - 1)
        {
            if (row + 1 < ans)
            {
                ans = row + 1;
                foo(ans);
            }
            return;
        }
    }
    for (int i = col + 1; i < n; i++)
    {
        if (mark[i] || remain < len[i])
            continue;
        arr[row][i] = 1, mark[i] = 1;
        dfs(row, i, remain - len[i] - W);
        arr[row][i] = 0, mark[i] = 0;
    }
    dfs(row + 1, -1, L);
}

int main()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            arr[i][j] = 0;
        mark[i] = 0;
    }
    dfs(0, -1, L);
    return 0;
}

目标函数： min n n’L can split to len[] 最小的n,使的n个长度为L的木板能够分割为长度为数组len的木板。

目标函数的界限：size(len) 最多需要n个木料就能切割出n块木板。

约束条件：remain>=len[i] 剩余的木料长度大于等与需要切割的木板长度。

限界函数：当前使用木板数量+剩余需要切割木板数量 这里用的递归所以没用到限界函数。

0%