本文共 1916 字，大约阅读时间需要 6 分钟。
大致题意：给定T和N个数，在N个数当中选出一些数相加，得到sum，你的任务就是要使sum<=T且T-sum要尽可能小，最后按照编号顺序输出你的方案，最后再输出sum。如果有多个方案，编号小的优先。
限制条件：1<=N<=50, 1<=T<=1000. 这道题很坑的地方就是题中是没有给出T的范围的（本人是在CF上做的，至少在CF上是没有的），只给出N的范围。所以刚开始看到这道题是考虑用折半搜索，然而实现的方法不对导致超时。之后偶然发现T的范围后才改用01背包去做。如果用01背包做的话，那么原题就转化为了，给定一个容量T的背包，有N个物品，每个物品都有一个体积，你的任务就是从这N个物品中挑出一些物品尽可能的填满这个背包。最后输出你的挑选方案。
设sum为挑出来的这些物品的体积之和，sum还是很容易就求出来的，关键是挑选方案。那么我们考虑回溯？因为DP也是可以用回溯找出方案的？可以，不过可能会很麻烦，不得已不建议。那要咋办？观察一下N的大小，N最大为50，250是在long long以内的，既然如此，我们就可以用一个二进制数来表示这个方案。举个例子：
Input: 5 5 1 2 3 4 5 output: 1 4 5 那么选1,4的方案就可以表示为(10010)=18。 但是题意是要求如果有多个方案，要输出编号小的，例如上述例子也可以选2,3，但最终是输出1,4。这个要如何判断？ 选择1,4的方案为(10010)=18，选择2,3的方案为(01100)=12，可以发现18>12。实际上，假设方案1用二进制数表示为k1，方案2用二进制数表示为k2，如果k1>k2，我们就选k1，否则选k2（可以自行多写几个样例验证一下）。代码如下：
#include#include #include #include using namespace std;typedef long long ll;const int maxn=1e3+5;int n,T;ll a[55];struct node{ bool flag; //dp[i][j].flag表示前i种物品能否填满容量为j的背包 ll sum; //dp[i][j[.sum表示前i中物品填满容量为j的背包的方案}dp[55][maxn]; int main(){ while(~scanf("%d",&T)) { if(!T) break; scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%lld",&a[i]); for(int i=0;i<=n;++i) for(int j=0;j<=T;j++) dp[i][j].flag=dp[i][j].sum=0; for(int i=0;i<=n;++i) dp[i][0].flag=1; for(int i=1;i<=n;++i) { for(int j=1;j<=T;++j) { dp[i][j]=dp[i-1][j]; //这一步别忘了 if(j>=a[i]) { if(dp[i-1][j-a[i]].flag) { if(!dp[i][j].sum) { dp[i][j].flag=1; dp[i][j].sum=dp[i-1][j-a[i]].sum+(1ll<<(n-i)); //额...一开始1没有加llWA了1次，记得加 } else if(dp[i-1][j-a[i]].sum+(1ll<<(n-i))>dp[i][j].sum) //>就行，是不会=的 { dp[i][j].flag=1; dp[i][j].sum=dp[i-1][j-a[i]].sum+(1ll<<(n-i)); } } } } } int ans=0;ll sum=0; for(int i=T;i>=1;i--) if(dp[n][i].flag) { ans=i; sum=dp[n][i].sum; break; } for(int i=n;i>=1;--i) { if(1ll&(sum>>(i-1))) printf("%d ",a[n-i+1]); } printf("%d\n",ans); } return 0;}
转载地址：http://twdci.baihongyu.com/