ZZY的爱好
题目：
Time Limit:1000MS Memory Limit:65536KTotal Submissions:3 Accepted:3
[Submit] [Go Back] [Status]
Description
ZZY爱足球、爱音乐、爱日剧、爱电影、爱A题、爱萌妹......总之ZZY喜欢做很多事情，而且ZZY希望在这些爱好中能收获一些东西，但是并不是所有爱好对所有收获目标都是起积极作用的，ZZY十分的困惑。于是ZZY列了下自己的收获目标并且给每个目标设立了最小要达到的权值，另外他将每个爱好对各个目标的影响进行了估值。这个值若是负则代表不利于获得某个收获，为0代表没影响，为正的代表利于获得某种收获。现在ZZY已经制作好了这些数据想请你帮帮忙，在保证所有的目标最低要求都能达成的情况下保留尽量多的爱好。
Input
多组数据读到EOF结束(不超过10组)每组数据，第一行为ZZY的收获目标个数N ( 0<N<=20 )，第二行为ZZY对每个目标所订的一个最低权值( 0 < w <= 1000 )，第三行为ZZY的爱好总数M ( 0 < M <= 16 )，下面的M行每行有N个数代表每个爱好对各个目标的促进权值( -1000 <= k <= 1000 )。
Output
每组输入对应一行输出：第一个数为能保留的最多爱好个数，紧接着为这些爱好的编号。若有多种都能达到保留个数请输出相对来说较小的(如1 2 与3 4 同时能满足要求，那么选1 2)。若怎么都无法实现目标那只能说着所有爱好都要不得，输出0。
Sample Input
4100 200 300 4003100 100 400 500 100 -10 50 300100 100 -50 -50
Sample Output
2 1 3
收获：一直这种题目不知道处理，今天终于知道了处理方法（虽然不怎么懂原理）。
思路：暴力枚举每一种情况如选择1 2 3 12 13 23 123 算出每种情况的解比较哪一种最优（就是那个暴力枚举不知道怎么暴^_^）
AC代码：
#include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; int v,g,a[31],i,j,s[31][31],p,k,num,ans[31],sum[31],m; int t[31],tnum; int main() { while (~scanf("%d",&v)) { for (i=1;i<=v;i++) scanf("%d",&a[i]); scanf("%d",&g); for (i=1;i<=g;i++) for (j=1;j<=v;j++) scanf("%d",&s[i][j]); p=(int)pow(2,g); //枚举共有p种情况 num=0; for (k=1;k<p;k++) { tnum=0; i=k; j=0; memset(sum,0,sizeof(sum)); while (i) //这个循环不懂，但就是实现了枚举的效果 { j++; if (i%2) { for (m=1;m<=v;m++) sum[m]+=s[j][m]; t[++tnum]=j; //记录选择的是那几个爱好 } i/=2; } for (m=1;m<=v;m++) if (sum[m]<a[m]) goto A; //判断是否满足要求 if (tnum>num) //如果爱好个数更多，则更新 { num=tnum; for (m=1;m<=num;m++) ans[m]=t[m]; }else if (tnum==num) //如果是12 和34爱好则要选12爱好 { for (m=1;m<=num;m++) if (ans[m]<t[m]) goto A; for (m=1;m<=num;m++) ans[m]=t[m]; } A: ; } printf("%d",num); for (i=1;i<=num;i++) printf(" %d",ans[i]); printf("\n"); } return 0; }
