<题目链接>
题目大意：
有n个瓶子，各有水量和容量。现在要将这写瓶子里的水存入最少的瓶子里。问你最少需要的瓶子数？在保证瓶子数最少的情况下，要求转移的水量最少。
解题分析：
首先，最少的瓶子数肯定可以通过贪心来简单求解。然后就是将所有瓶子的水量作为01背包的总体积，然后就是$dp[i][j]$表示前$i$个物品选了水量为$j$的最大容量。本题的这种逆向思维有点像那道小偷抢银行的01背包题。但是因为本题规定了需要选取的那些容量大的物品，所以略有不同。对这$n$个物品进行01背包，杯子的水量看成体积，容量看成价值，同时枚举上一个物品，进行状态的转移。最后倒序遍历水量，一旦碰到容量大于等于总水量的情况即可输出。
#include <bits/stdc++.h>
using namespace std; const int N = ;
int n,sum,dp[N][N*N];
//dp[i][j]表示前i个物品水量为j(所选物品的水量之和)的最小容量 struct Node{ int flow,cal; }node[N]; inline bool cmp(Node tmp1,Node tmp2){ return tmp1.cal>tmp2.cal; } int main(){
cin>>n;
for(int i=;i<=n;i++)
cin>>node[i].flow,sum+=node[i].flow;
for(int i=;i<=n;i++)cin>>node[i].cal;
sort(node+,node++n,cmp);
int totcal=,num;
for(int i=;i<=n;i++){
totcal+=node[i].cal;
if(totcal>=sum){ num=i;break; } //求解出最少需要多少个杯子
}
memset(dp,-,sizeof(dp));
dp[][]=;
for(int i=;i<=n;i++){ //将水量看成体积，将容量看成价值
for(int j=sum;j>=node[i].flow;j--){
for(int pre=i-;pre>=;pre--) if(dp[pre][j-node[i].flow]!=-){ //枚举上一个物品，进行状态的转移
dp[pre+][j]=max(dp[pre+][j],dp[pre][j-node[i].flow]+node[i].cal);
}
}
}
int loc;
for(int i=sum;i>=;i--) if(dp[num][i]>=sum){ //找到符合要求的最大流量
loc=i;break;
}
printf("%d %d\n",num,sum-loc); //sum-loc即需要转移的流量
}