swust594 Maximum Tape Utilization Ratio
Maximum Tape Utilization Ratio
1000(ms)
65535(kb)
819 / 2662
设有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;
}
Momenta公司福利 293人发布