度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。
百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。
但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)
Input第一行一个整数T，表示T组数据。每组测试数据将以如下格式从标准输入读入：
B
N
score_1 cost_1
score_2 cost_2
:
score_N cost_N
第一行，正整数B（0 <= B <= 1000），代表午餐的预算。
第二行，正整数N (0 <= N <= 100)，代表午餐可选的菜品数量
从第三行到第 (N + 2) 行，每行两个正整数，以空格分隔，score_i表示菜品的得分，cost_i表示菜品的价格(0 <= score_i, cost_i <= 100)。
Output对于每组数据，输出两行：第一行输出："Case #i:"。i代表第i组测试数据。第二行输出菜品的总得分和总花费，以空格分隔。第三行输出所选菜品的序号，菜品序号从1开始，以空格分隔。
Sample Input 2 29 6 9 10 3 4 6 5 7 20 10 9 15 11 0 2 2 23 10 12 Sample Output Case #1: 34 29 2 3 5 6 Case #2: 0 0明显的01背包问题，只要注意下记录选取的顺序
有点小坑在于，题目的price可以取0，所以我们在选择时，背包的容量要是从0-B
以及最后输出的时候，没有最优选择策略时，注意最后的换行
#include <iostream> #include <cstring> #include <stack> #include <cstdio> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <set> #include <map> const double eps=1e-8; const double PI=acos(-1.0); using namespace std; struct food { int score; int price; } f[1050]; int m[1050][1050];//dp int select[1050][1050];//选择的存储 int ans[1050];//路径存储 int main() { int t; scanf("%d",&t); int cas=1; while(t--) { memset(select,0,sizeof(select)); memset(ans,0,sizeof(ans)); memset(m,0,sizeof(m)); memset(f,0,sizeof(f)); int all; int n; scanf("%d%d",&all,&n); for(int i=1; i<=n; i++) scanf("%d%d",&f[i].score,&f[i].price); for(int i=1; i<=n; i++) { for(int j=0;j<=all;j++)//背包容量要从0-all（总容量）. if(f[i].price<=j){ m[i][j]=max(m[i-1][j],m[i-1][j-f[i].price]+f[i].score); if(m[i][j]==m[i-1][j]) select[i][j]=0;//选取为1，反之为0； else select[i][j]=1; } else{ m[i][j]=m[i-1][j]; select[i][j]=0; } } int j=0; int all1=all; int cost=0; for(int i=n;i>=1;i--)//逆序得路径 if(select[i][all]==1){ ans[j++]=i; all-=f[i].price; cost+=f[i].price;//总花费 } printf("Case #%d:\n",cas++); printf("%d %d\n",m[n][all1],cost); if(j)//注意格式的输出 printf("%d",ans[j-1]); for(int i=j-2;i>=0;i--) printf(" %d",ans[i]); if(j) printf("\n"); } return 0; }
