Maximum Tape Utilization Ratio
1000(ms)
65535(kb)
956 / 3237
设有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
这道题算是被标签写的贪心给骗了，其实这道题是一道动态规划加贪心的题。
代码如下：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[605][6005][2];
//dp[i][j][0]表示在程序数n、磁带长度为j的情况下 ，最多可以存储的程序数
// dp[i][j][0]表示在程序数n、磁带长度为j的情况下 ，程序最多情况时的磁带长度
int count[605];
int len[605];
int main()
{int n,l;cin>>n>>l;for(int i=1;i<=n;i++){cin>>len[n+1-i];}memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){for(int j=0;j<=l;j++){if(len[i]<=j && dp[i-1][j][0]<dp[i-1][j-len[i]][0]+1){dp[i][j][0]=dp[i-1][j-len[i]][0]+1;dp[i][j][1]=dp[i-1][j-len[i]][1]+len[i];}else if(len[i]<=j && dp[i-1][j][0]==dp[i-1][j-len[i]][0]+1){dp[i][j][0]=dp[i-1][j][0];dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-len[i]][1]+len[i]);}else{dp[i][j][0]=dp[i-1][j][0];dp[i][j][1]=dp[i-1][j][1];}}}cout<<dp[n][l][0]<<" "<<dp[n][l][1]<<endl;int j=dp[n][l][1],k=1,i=n;while(i--){if(dp[i][j][0]==dp[i-1][j-len[i]][0]+1&&dp[i][j][1]==dp[i-1][j-len[i]][1]+len[i]);{j-=len[i];count[k++]=len[i];}}for(k=1;k<=dp[n][s][0];k++){if(k!=1) cout<<' ';cout<<count[k];}cout<<endl;return 0;
}