swust594 Maximum Tape Utilization Ratio

Maximum Tape Utilization Ratio

 1000(ms)

 65535(kb)

 819 / 2662

Tags: 贪婪策略

设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是li ，1 < = i < = n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。在保证存储最多程序的前提下还要求磁带的利用率达到最大。 对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数和占用磁带的长度。

输入

第一行是2 个正整数，分别表示文件个数n <=600和磁带的长度L<=6000。接下来的1 行中，有n个正整数，表示程序存放在磁带上的长度。

输出

第1 行输出最多可以存储的程序数和占用磁带的长度；第2行输出存放在磁带上的每个程序的长度。

样例输入

9 50
2 3 13 8 80 20 21 22 23

样例输出

5 49
2 3 13 8 23

简单背包加路径搜索，mad题目上给的贪心我就真的贪心了……还因为改了i=1没改下面的n-1然后很神奇的在找bug……也是醉醉的。

#include<iostream>
#include<algorithm>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<queue>
using namespace std;
#define INT_MAX 2147483647
#define ll long long int

int dp[605][6005][2];
int path[605];
int ci[605];

int main()
{

	int n, l;
	int i, j, k;
	while (~scanf("%d %d", &n, &l))
	{
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &ci[n+1-i]);
		}

		memset(dp, 0, sizeof(dp));

		for (i = 1; i <= n; i++)
		{
			for (j = 0; j <= l; j++)
			{

				if (ci[i] <= j && dp[i - 1][j][0] < dp[i - 1][j - ci[i]][0] + 1)
				{
					dp[i][j][0] = dp[i - 1][j - ci[i]][0] + 1;
					dp[i][j][1] = dp[i - 1][j - ci[i]][1] + ci[i];
				}
				else if (ci[i] <= j && dp[i - 1][j][0] == dp[i - 1][j - ci[i]][0] + 1)
				{
					dp[i][j][0] = dp[i - 1][j][0] ;
					dp[i][j][1] = max(dp[i - 1][j - ci[i]][1] + ci[i], dp[i - 1][j][1]);
				}
				else
				{
					dp[i][j][0] = dp[i - 1][j][0];
					dp[i][j][1] = dp[i - 1][j][1];
				}

			}
		}

		printf("%d %d\n", dp[n][l][0], dp[n][l][1]);
		i = n;
		j = dp[n][l][1];
		k = 1;
		while (i)
		{
			if (dp[i][j][0] == dp[i - 1][j - ci[i]][0] + 1 && dp[i][j][1] == dp[i - 1][j - ci[i]][1] + ci[i])
			{
				j -= ci[i];
				path[k++] = ci[i];
			}
			i--;
		}

		for (int k = 1; k <= dp[n][l][0]; k++)
		{
			if (k != 1)
			{
				cout << " ";
			}
			printf("%d", path[k]);
		}
		cout << endl;
	}

	return 0;

}