文件什么上传到wordpress/北京seo助理
设有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
首先，我去网上搜索这道题的时候全都是只有代码没有题解的，最气的是还全是一个代码QWQ，所以就想写这篇博客并且写出清晰的解题思路。
其次，这oj的tag太水了吧（贪婪策略）其实并不是，这是一道动态规划题目。
题解：
思路一：
我们开一个结构体存三个信息：可存程序个数，磁带占用长度，所有的程序
dp[j].count 表示磁带长度为j最多可以存的程序的个数
dp[j].sumv 表示磁带长度为j最多可以占用的磁带长度
dp[j].pre 表示存了count个程序的每个程序占用的磁带长度
首先我们要满足储存的程序数最多那么如果满足：dp[j].count < dp[j - s].count + 1，可更新数据。
当储存程序相同的时候，我们需要满足：dp[j].sumv <= (dp[j - s].sumv + s)，即程序数目相同的情况下，需要最大的磁带占用率，如果满足更新数据。
然后就可以进行求解了，动态规划走一波：（题目坑点：输出最小字典序的程序）
坑点测试数据：
5 8
2 4 4 6 8
ans is
2 8
2 6(not 4 4)核心代码：
//注意倒序,for (int i = n - 1; i >= 0; i--) {int s;s = num[i];for (int j = m; j >= 0; j--) {if (j - s >= 0) {if (dp[j].count < dp[j - s].count + 1||(dp[j].count == (dp[j - s].count + 1)&& dp[j].sumv <= (dp[j - s].sumv + s)) ) {//注意等于：：等于的时候直接覆盖掉，这样求出来的是最大的字典序dp[j].count = dp[j - s].count + 1; //但是我们是用的倒叙，所以反过来就是最小字典序dp[j].pre = dp[j - s].pre;dp[j].pre.push_back(s);dp[j].sumv = dp[j - s].sumv + s;}}}}完整代码：
#include<iostream>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<map>
#include<string>
#include<stdio.h>
#include<vector>
#include<string>
#include<time.h>
#include<stack>
using namespace std;
#define LL long long int
#define mod 1000000007
#define MAX(x, y) (x) > (y) ? (x) : (y)
using namespace std;
#define PI 3.14159265354struct node {int sumv;int count;vector<LL>pre;node() {sumv = 0;count = 0;pre.clear();}
};
int main()
{ios::sync_with_stdio(false);int n, m;while (cin >> n >> m) {node dp[6005];int num[605];for (int i = 0; i < n; i++)cin >> num[i];//注意倒序,for (int i = n - 1; i >= 0; i--) {int s;s = num[i];for (int j = m; j >= 0; j--) {if (j - s >= 0) {if (dp[j].count < dp[j - s].count + 1||(dp[j].count == (dp[j - s].count + 1)&& dp[j].sumv <= (dp[j - s].sumv + s)) ) {//注意等于：：等于的时候直接覆盖掉，这样求出来的是最大的字典序dp[j].count = dp[j - s].count + 1; //，但是我们是用的倒叙，所以反过来就是最小字典序dp[j].pre = dp[j - s].pre;dp[j].pre.push_back(s);dp[j].sumv = dp[j - s].sumv + s;}}}}cout << dp[m].count << ' ' << dp[m].sumv << endl;int len = dp[m].pre.size();//倒叙输出for (int i = len-1; i >=0 ; i--) {if (i != len-1)cout << ' ';cout << dp[m].pre[i];}cout << endl;}return 0;
}
思路二：
由于本题数据较小其实可以采用DFS求解：
先求出最多可以储存的程序的个数，然后进行DFS找出最小字典序以及最大磁带利用率的程序，我看后台时发现有人是这么过的QWQ，实测可以过，代码就不贴了，你们懂的QWQ..........