Installing Apps Gym - 101623I（背包+贪心）

本文主要是介绍Installing Apps Gym - 101623I（背包+贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
下载app，每个app有下载容量和安装容量。内存必须满足下载容量才能下载，最后所占空间为安装容量。
求c的内存最多可以安装多少个app。

思路：
比赛的时候wzf猜了个结论，就是按照 d-s排序从大到小遍历，然后按照普通背包跑然后过了。

事后想想的话，其实可以从背包转移方程看出来：
$dp[j-num+a[i].s]=max(dp[j-num+a[i].s],dp[j-num]+1)，num=max(a[i].s,a[i].d)，num\le j\le c$
可以看出来，$d-s$越大，就会有越多的状态更新不到，就像是减少了c的大小。将$d-s$大的放前面可以使得这些不能更新到的状态值尽可能小，“损失”也就尽可能小。
所以$d-s$大的放在前面可以尽可能的使得预留的空间大，使得能尽量装下这些物品。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 10005;int dp[maxn],pre[505][maxn];struct Node {int d,s;int id;
}a[maxn];int cmp(Node a,Node b) {return a.d - a.s > b.d - b.s;
}int main() {int n,c;scanf("%d%d",&n,&c);for(int i = 1;i <= n;i++) {scanf("%d%d",&a[i].d,&a[i].s);a[i].id = i;}sort(a + 1,a + 1 + n,cmp);for(int i = 1;i <= n;i++) {int num = max(a[i].d,a[i].s);for(int j = 0;j <= c;j++) pre[i][j] = j;for(int j = c;j >= num;j--) {if(dp[j - num + a[i].s] < dp[j - num] + 1) {pre[i][j - num + a[i].s] = j - num;dp[j - num + a[i].s] = dp[j - num] + 1;}}}int mx = 0,pos = 0;for(int i = 1;i <= c;i++) {if(dp[i] > mx) {mx = dp[i];pos = i;}}vector<int>ans;for(int i = n;i >= 1;i--) {if(pre[i][pos] != pos) {ans.push_back(a[i].id);pos = pre[i][pos];}}printf("%d\n",ans.size());reverse(ans.begin(), ans.end());for(int i = 0;i < ans.size();i++) {printf("%d ",ans[i]);}return 0;
}

这篇关于Installing Apps Gym - 101623I（背包+贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---