題干：

In Zhejiang University Programming Contest, a team is called "couple team" if it consists of only two students loving each other. In the contest, the team will get a lovely balloon with unique color for each problem they solved. Since the girl would prefer pink balloon rather than black balloon, each color is assigned a value to measure its attractiveness. Usually, the boy is good at programming while the girl is charming. The boy wishes to solve problems as many as possible. However, the girl cares more about the lovely balloons. Of course, the boy's primary goal is to make the girl happy rather than win a prize in the contest.

Suppose for each problem, the boy already knows how much time he needs to solve it. Please help him make a plan to solve these problems in strategic order so that he can maximize the total attractiveness value of balloons they get before the contest ends. Under this condition, he wants to solve problems as many as possible. If there are many ways to achieve this goal, he needs to minimize the total penalty time. The penalty time of a problem is equal to the submission time of the correct solution. We assume that the boy is so clever that he always submit the correct solution.

Input

The first line of input is an integer?N?(N?< 50) indicating the number of test cases. For each case, first there is a line containing 2 integers?T?(T?<= 1000) and?n?(n?<= 50) indicating the contest length and the number of problems. The next line contains?n?integers and the?i-th integer?ti?(ti?<= 1000) represents the time needed to solve the ith problem. Finally, there is another line containing?n?integers and the?i-th integer?vi?(vi?<= 1000) represents the attractiveness value of the?i-th problem. Time is measured in minutes.

Output

For each case, output a single line containing 3 integers in this order: the total attractiveness value, the number of problems solved, the total penalty time. The 3 integers should be separated by a space.

Sample Input

2 300 10 10 10 10 10 10 10 10 10 10 10 1 2 3 4 5 6 7 8 9 10 300 10 301 301 301 301 301 301 301 301 301 301 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

Sample Output

55 10 550 0 0 0

題目大意：

給出比賽時間和題目數，并給出每道題目的耗時以及獲得的價值，求所能獲得的最大價值，以及獲得這個最大價值下的最多題目數以及該情況的最小最少罰時（罰時為每道題目提交的時間之和）。

解題報告：

? ?首先將這個時間序列問題轉化成背包問題，然后考慮：假設最終選定了這些題目，那么最終價值和解題數都是一定的，但是為了得到最小罰時，我們需要貪心先做時間最短的題目，所以我們不妨先按照時間順序排序。這樣就不需要記錄最終選擇了哪些題了。（否則需要記錄選擇了哪些題目，然后再排序求ans3，十分不劃算）

? 然后就是01背包，背包的同時維護這三個信息。

剛開始總是想著兩次背包，先背出最大價值，然后再背包出最優解題數，同時維護ans3，，。。反正是WA了、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n,T; struct Node {ll val,t; } node[MAX]; struct N {ll val,num,t;N(){}N(ll val,ll num,ll t):val(val),num(num),t(t){}bool operator<(const N b)const{if(val != b.val) return val < b.val;if(num != b.num) return num < b.num;return t > b.t;} } dp[MAX]; bool cmp(Node a,Node b) {return a.t < b.t; } int main() {int t;cin>>t;while(t--) {scanf("%d%d",&T,&n);memset(dp,0,sizeof dp);for(int i = 1; i<=n; i++) scanf("%lld",&node[i].t);for(int i = 1; i<=n; i++) scanf("%lld",&node[i].val);sort(node+1,node+n+1,cmp);N ans = N(0,0,0);for(int i = 1; i<=n; i++) {for(int j = T; j>=node[i].t; j--) {N pre = dp[j-node[i].t];N tmp = N(pre.val + node[i].val,pre.num + 1,pre.t + j);if(dp[j] < tmp) dp[j] = tmp;if(ans < dp[j]) ans = dp[j];}}printf("%lld %lld %lld\n",ans.val,ans.num,ans.t);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【ZOJ - 3703】Happy Programming Contest（带优先级的01背包，贪心背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。