I - Installing Apps 贪心+01背包
题目大意：
有n种手机软件，每一种软件的安装包大小是d，安装后的软件大小是s(删除了安装包)，那么若有c的手机内存，最多能安装多少个手机软件
题解：
贪心，用微调法可以确定贪心的策略，也就是排序的依据。
微调法就是调整前后两个的顺序，来求需要的容量，越小的在越前面。
然后就是一个01背包，但是01背包写的好搓。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxn = 550;
struct node{
int d,s,id;
node(int d=0,int s=0,int id=0):d(d),s(s),id(id){}
}e[maxn];
bool cmp(node a,node b){
return max(a.s,a.d)-a.s>max(b.d,b.s)-b.s;
}
int dp[maxn][11000];
/**
dp[i][j] 表示对于前面i个物品，选择之后花费了j的容量下载的最大的数量
**/
vector<int>a;
int main(){
int n,c;
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
e[i] = node(x,y,i);
}
sort(e+1,e+1+n,cmp);
memset(dp,0xef,sizeof(dp));
dp[0][0] = 0;
int ans = 0,pos = 0,v = 0;
for(int i=1;i<=n;i++){
// printf("i = %d s = %d d = %d\n", i,e[i].s,e[i].d);
for(int j=0;j<=c;j++){
if(c-j>=e[i].s&&c-j>=e[i].d){
// printf("j = %d\n", j);
dp[i][j+e[i].s]=max(dp[i][j+e[i].s],dp[i-1][j]+1);
// printf("dp[%d][%d]=%d\n", i,j+e[i].s,dp[i][j+e[i].s]);
if(dp[i][j+e[i].s]>ans){
ans = dp[i][j+e[i].s];
pos = j+e[i].s;
v = i;
}
}
dp[i][j] = max(dp[i][j],dp[i-1][j]);
}
}
a.clear();
while(v>0){
if(dp[v][pos]==dp[v-1][pos-e[v].s]+1) pos = pos-e[v].s,a.push_back(e[v].id);
v = v - 1;
}
printf("%d\n", ans);
for(int i=a.size()-1;i>=0;i--) printf("%d ", a[i]);
printf("\n");
}