Installing Apps(贪心+01背包)

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

5008: Installing Apps

时间限制: 2 Sec   内存限制: 128 MB
提交: 163   解决: 22
[ 提交][ 状态][ 讨论版][命题人: admin]

题目描述

输入

输出

样例输入

2 100

99 1

1 99

样例输出

2

提示

来源

题意：有n种手机软件，每一种软件的安装包大小是d，安装后的软件大小是s(删除了安装包)，那么若有c的手机内存，最多能安装多少个手机软件。

题解：按照贪心原则，可按安装包和软件大小的差值进行排序，同时在装背包的时候要考虑是否能装进d，即c-j>=d-s

#include<stdio.h>
#include <algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
#define gcd(a,b) __gcd(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}
struct node
{int d,s,m;
}e[11000];
int n,c;
int cmp(node a,node b)
{return a.d-a.s>b.d-b.s;
}int dp[30000305];
int main()
{int i,j;scanf("%d%d",&n,&c);for(i=1;i<=n;i++)scanf("%d%d",&e[i].d,&e[i].s);sort(e+1,e+1+n,cmp);int ans=0;for(i=1;i<=n;i++)for(j=c;j>=e[i].s;j--)if(c-j>=e[i].d-e[i].s)dp[j]=max(dp[j],dp[j-e[i].s]+1),ans=max(ans,dp[j]);printf("%d\n",ans);return 0;
}

这篇关于Installing Apps(贪心+01背包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---