ZOJ1213-Lumber Cutting—动态规划的实现

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;

struct stBoard
{
	int number, length;
	stBoard () {number = 1000;}	//木板数量的最优值，初值为∞
};

bool operator < (const stBoard &op1, const stBoard &op2)
{
	if(op1.number == op2.number)
		return op1.length > op2.length;
	return op1.number < op2.number;
}

int dp(int n, int board, int saw, int *part)
{
	stBoard plank[4096];
	plank[0].length = plank[0].number = 0;
	int count = (1 << n) - 1;
	for(int i = 0; i < count; i++)
		for(int j = 0; j < n; j++)
		{
			int index = i | 1 << j;	// 处理木料j
			if(index != i) // 木料j以前处理过
			{	
				stBoard now = plank[i];
				if(now.length >= part[j])
					//调整剩余木料的长度
					now.length -= part[j];
				else	//不能安排第i个木料
				{	//增加1个木料
					now.number++;
					now.length = board - part[j];
				}
				//调整剩余木料的长度
				now.length = max(now.length - saw, 0);
				//调整最优值
				plank[index] = min(plank[index], now);				
			}
		}
	return plank[count].number;
}


int main()
{
	printf("Problem 7 by team x\n");
	char c;
	int part[13];	//要切割的木料
	int board, saw;	//木板的长度，锯的宽度
	while(scanf("%d", &board) != EOF)	//读取木板的长度
	{	
		scanf("%d", &saw);				//读取木板的宽度
		int n = 0;			//木料的数量
		while((c = getc(stdin)) != '\n')//判断回车
		{	
			ungetc(c, stdin);	//将字符c退回缓冲区
			scanf("%d", part+n++);
		}
		printf("\n");
		printf("Board length            =%6d\n", board);
		printf("Saw width               =%6d\n", saw);
		printf("Number of boards needed =%6d\n", dp(n, board, saw, part));
	}
	printf("End of problem 7 by team x\n");
	return 0;
}