测试输入包含若干测试用例。每个测试用例的第1行包含一个整数N (<=30),随后有N行,每行给出一场bg的信息: h l t 其中 h 是快乐度,l是持续时间(小时),t是发起人离校时间。数据保证l不大于t,因为若发起人必须在t小时后离开,bg必须在主人离开前结束。 当N为负数时输入结束。
每个测试用例的输出占一行,输出最大快乐度。
3 6 3 3 3 2 2 4 1 3 4 5 1 1 10 2 3 6 1 2 3 1 1 -1
7 16
/* 这道题在第一眼看的时候,觉得应该用贪心算法,但说实话个人觉得贪心算法就好像打赌一样 ,这种五五开的算法个人不是很敢用。 因此我开始尝试其他解法。首先想到的就枚举,但是枚举太耗时。转念一想,暴力枚举的另一种表现 形式那毫无疑问就是搜索了,因此这道题可以考虑用搜索策略来解决 单纯的搜索肯定会超时,因此这道题还需要进行剪枝。剪枝的依据就是根据参加bg的人必须在活动结束 前离开会场。 与此同时,在搜索之前还应该按照活动结束的时间进行排序,否则不一定能得到最优的结果 */ #include <stdio.h> #include <string.h> #define MAX 40 struct Info { int h; int l; int t; }; struct Info happy[MAX]; int N,M; int maxi; void DFS(int i,int sum,int now) { if(i==N){ if(sum>maxi) { maxi=sum; } return; } DFS(i+1,sum,now); if(now+happy[i].l<=happy[i].t) { DFS(i+1,sum+happy[i].h,now+happy[i].l); } } void sort() { int i,j,k; for(i=0;i<N;i++) { k=i; for(j=i;j<N;j++) { if(happy[j].t<happy[k].t) { k=j; } } struct Info temp=happy[i]; happy[i]=happy[k]; happy[k]=temp; } } int main() { int h,l,t; int a,b; int i; while(scanf("%d",&N)!=EOF&&N>=0) { for(i=0;i<N;i++) { scanf("%d %d %d",&happy[i].h,&happy[i].l,&happy[i].t); } maxi=-1; sort(); DFS(0,0,0); printf("%d\n",maxi); } }
dfs妥妥的超时了,背包可过
package com.speical.improve;
import java.util.Scanner;
/**
* 背包问题
*
* 变形的背包的问题,这里加入了时间顺序
* 对应到背包问题上,就是多少体积内只准装哪个物体
* 传统的背包问题的递推公式为: dp[j] = max{dp[j], dp[j - v[i]] + w[i]]
* 然后的这里的递推公式也是这样,只不过,加上了前提条件
* 要判断该饭局是否能在这个时间段。j - nodes[i].duration <= nodes[i].lateStartTime(不能超过最迟开始时间)
*
* 这里很重要的一点,就是要事先对所有的活动按照结束时间从小到大排序
* 这样在考虑结束完的活动就可以利用结束早的活动中间状态
* 因为我们的思想仅仅是计算某个时间段的最大值,且我这里的内循环仅从该活动的结束时间往前算的
* 所以最后dp[maxTime]并不能记录最大,我这里的dp[j],仅仅记录活动的时间正好为j对应的最大值。
* 所以我用了一个全局max来记录最大
* @author special
* @date 2018年1月22日 上午9:22:23
*/
public class Pro137Improve1 {
static class Node{
int price;
int duration;
int end;
int lateStartTime;
public Node(int price, int duration, int end, int lateStartTime){
this.price = price;
this.duration = duration;
this.end = end;
this.lateStartTime = lateStartTime;
}
}
public static void insertSort(Node[] nodes){
for(int i = 1; i < nodes.length; i++){
for(int j = i; j > 0 && nodes[j].end < nodes[j - 1].end; j--){
Node temp = nodes[j];
nodes[j] = nodes[j - 1];
nodes[j - 1] = temp;
}
}
}
public static int getMaxPrice(Node[] nodes, int maxTime){
int max = Integer.MIN_VALUE;
int[] dp = new int[maxTime + 1];
for(int i = 0; i < nodes.length; i++){
for(int j = nodes[i].end; j >= nodes[i].duration; j--){ //从该活动的结束时间往前算
if(j - nodes[i].duration <= nodes[i].lateStartTime){
dp[j] = Math.max(dp[j], dp[j - nodes[i].duration] + nodes[i].price);
max = Math.max(max,dp[j]);
}
}
}
return max;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int n = input.nextInt();
if(n == -1) break;
Node[] nodes = new Node[n];
int price, duration, end, maxTime = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
price = input.nextInt();
duration = input.nextInt();
end = input.nextInt();
nodes[i] = new Node(price, duration, end, end - duration);
maxTime = Math.max(maxTime, end);
}
insertSort(nodes);
System.out.println(getMaxPrice(nodes, maxTime));
}
}
}
/////////////使用两种方法来解决此问题,方法1为中规中矩的动态规划,方法2使用了滚动数组看起来简单,但是非常巧妙要想清楚。///////// //1.使用动态规划来解决// //满足最优子结构 //活动已经按照最大结束时间非递减排序,以便于后面计算的时候利用前面的计算结果,即重复子问题 //目标函数DP[i][j]:考虑前i个BG且最大离开时间为j所能获得的最大欢乐度, j = 0,1,2... //状态转移方程: //margin = j - bgs[i].duration, j ∈ [bgs[i]duration, bgs[i]deadline] //在这个区间内,就是标准的0/1背包问题了 //DP[i][j] = max(DP[i - 1][j], bgs[i].happiness + DP[i - 1][margin]); #include <iostream> (720)#include <algorithm> #include <vector> using namespace std; struct BG { int happiness; int duration; int deadline; bool operator < (const BG a)const { return deadline < a.deadline; } }; int main() { int n; vector<BG> bgs; vector<vector<int> > DP;//DP[i][j]只考虑前i个bg且最大离开时间为i所能获得的最大快乐度 while(cin >> n && n > 0) { bgs.clear(); bgs.resize(n); for(int i = 0 ; i < n ; ++i) { cin >> bgs[i].happiness >> bgs[i].duration >> bgs[i].deadline; } sort(bgs.begin(), bgs.end());//根据结束时间排序以便使用之前计算的结果进行递推 DP.clear(); DP.resize(n); int max_end = bgs.back().deadline; for(int i = 0; i < n; ++i){ DP[i].resize(max_end + 1, 0); } for(int j = 0; j < max_end+1; ++j){//初始化只有一个活动的情况 DP[0][j] = (j<bgs[0].duration ? 0 : bgs[0].happiness); } for(int i = 1; i < n; ++i) { for(int j = 0; j < max_end+1; ++j) { //加入i之后,它可以在区间[duration, deadline]内结束 if(j < bgs[i].duration){//时间太短无法完成此活动 DP[i][j] = DP[i - 1][j]; } else if(j > bgs[i].deadline){//时间已经超过最大结束时间,按照最大结束时间来算 DP[i][j] = DP[i][bgs[i].deadline]; } else {//在[duration, deadline]内结束,则为0/1背包问题 //若是选择活动i,则把此活动尽量后推结束,因为若能在此活动结束后再参加别的活动,则一定能在此活动开始前结束。 int margin = j - bgs[i].duration;//前面能插入的活动的最大结束时间 DP[i][j] = max(DP[i - 1][j], bgs[i].happiness + DP[i - 1][margin]); } //不一定是走的越晚,快乐度越高,例如(10,2,2)和(1,2,3) } } cout << DP[n-1][max_end] << endl; } return 0; } //方法2:使用滚动数组来解决 /* #include <iostream> #include <algorithm> #include <vector> using namespace std; struct BG { int happiness; int duration; int deadline; bool operator < (const BG a)const { return deadline < a.deadline; } }; int main() { int n; vector<BG> bgs; vector<int> DP;//DP[i]最大离开时间为i所能获得的最大快乐度 while(cin >> n && n > 0) { bgs.clear(); bgs.resize(n); for(int i = 0 ; i < n ; ++i) { cin >> bgs[i].happiness >> bgs[i].duration >> bgs[i].deadline; } sort(bgs.begin(), bgs.end()); DP.clear(); DP.resize(bgs.back().deadline +1, 0); int max_h = 0; for(int i = 0; i < n; ++i) { //若是选择活动i,则把此活动尽量后推结束,因为若能在此活动结束后再参加别的活动,则一定能在此活动开始前结束。 for(int j = bgs[i].deadline; j >= bgs[i].duration; --j) {//加入i之后,它可以在区间[duration, deadline]内结束,用这个bg来更新这个区间内的所有DP值 DP[j] = max(DP[j], bgs[i].happiness + DP[j-bgs[i].duration]); max_h = max(max_h, DP[j]);//注意后来的活动的实际结束时间可以比前面已有的最优解更早或者更优,只有将过程进行到底才能确定某个时刻离开的最大欢乐度。并非越晚离开越快乐(看完即走不发呆白等)。 } } cout << max_h << endl; } return 0; } */
/*最开始想到贪心,但此题不能用贪心!!以下是我的思考过程,可能细节上还有点毛病 关于贪心的使用————每个阶段的最优状态都是由上一个阶段的最优状态得到的 那么该问题的状态和阶段是什么呢? 现在来看关于阶段的定义,所谓阶段是指随着问题的解决,在同一个时刻可能会 得到的不同状态的集合。我们可以把时间作为划分阶段的尺度,那么就是第i小时, 就是第i阶段。因为本题要求最大快乐度,那么状态的对象一定是最大快乐度, 既然阶段是时间,那么怎么定义才能让一个阶段包含多个不同状态的集合,那就是 参加的不同活动的集合所带来的最大快乐度,对于本题,在一个给定的时间i可能 一个人参加了活动1,但他同样能通过参加活动2来获得同样的快乐度。现在考虑, 能不能符合————“每个阶段的最优状态都是由上一个阶段的最优状态得到”? 显然是不能的,例如上一个阶段,也就是第i小时的最优状态,必定是参加了某几个 活动而获得的最大快乐度。而来到了第i+1小时,现在又新增了能参加的活动,可是 若该活动的开始时间与之前的活动冲突,但其提供的最大快乐度又大于之前的状态, 明显,上一个阶段的最优状态并不能得到现阶段的最优解 现在,再来看动态规划 ->每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到 放到这一道题怎么理解呢,因为前一阶段所参加了的活动可能正好与更好的活动冲突, 我们可能需要跟之前的阶段,那个时候的状态能与现在这个更好的活动正好分隔开来, 而之前的这个阶段的状态也一定是通过某种方法得到的,我们可以不用关心他又是 怎么得来的,所以本题是符合动态规划的定义的!! 因此我们定义dp[j]为j时刻所获得的最大快乐度,通过遍历所有活动,在遍历所有时间 来转移所要的状态。在动态规划中又是背包的形式,状态转移方程就是, dp[j] = Max(dp[j - bg[i].time] + bg[i].joy,dp[j]) 其中j>=bg[i].time */ #include<cstdio> #include<algorithm> #include<vector> using namespace std; int Max(int x, int y); struct BG { int joy; int end; int time; bool operator < (const BG &b) const { return end < b.end; } }; int main() { int n; while(scanf("%d",&n) != EOF && n > 0) { int maxtime = 0; vector<BG> bg(n); for(int i = 0; i<n; i++) { scanf("%d%d%d",&bg[i].joy,&bg[i].time,&bg[i].end); maxtime = Max(maxtime,bg[i].end); }///////同时记录下离开的时间 sort(bg.begin(),bg.end()); //另外还要把每个活动最晚结束时间sort一下,不然不能保证某一阶段得到的是最优状态 vector<int> dp(maxtime + 1,0); int max = 0; //另外要有一个max来记录最大快乐度,最高快乐度的不一定是最晚结束的 for(int i = 0; i<n; i++) { for(int j = bg[i].end; j>=bg[i].time; j--) { dp[j] = Max(dp[j - bg[i].time] + bg[i].joy,dp[j]); max = Max(max,dp[j]); } }//这一部分就是典型背包的思想了,并且利用了滚动数组 printf("%d\n",max); }//while return 0; }//main int Max(int x, int y) { return x>y?x:y; }
基本思路:可转换为0-1背包问题,其中每一个bg都是一个可以放入背包的物品,bg的快乐度即为物品的总价值,而时间则是物品的体积。由于每个bg都有最晚离开时间和持续时间,即规定了每个bg可以开始的时间集合,这也就使得每一层状态的维度不是有序的,对状态转移造成错误,为了避免这种情况,需要对每个bg的最晚离开时间排序。#include <iostream> #include <algorithm> using namespace std; struct Event{ int happiness; int lastTime; int leaveTime; bool operator < (const Event a)const{ return leaveTime < a.leaveTime; } }; int N; int main(void){ while(cin >> N && N >= 0){ int dp[1000] = {0}; Event eventList[30]; for(int i = 0; i < N; i++){ cin >> eventList[i].happiness >> eventList[i].lastTime >> eventList[i].leaveTime; } sort(eventList, eventList + N); int maxValue = 0; for(int i = 0; i < N; i++){ for(int curTime = eventList[i].leaveTime; curTime >= eventList[i].lastTime; curTime--){ dp[curTime] = max(dp[curTime - eventList[i].lastTime] + eventList[i].happiness, dp[curTime]); maxValue = max(maxValue, dp[curTime]); } } cout << maxValue << endl; } return 0; }
#include <algorithm> #include <iostream> #include <vector> using namespace std; struct bg { int h; int l; int t; }; bool compare(const bg &b1, const bg &b2) { return b1.t < b2.t; } void dfs(vector<bg> &v, int pos, int t, int h, int &maxhappy) { for (unsigned i = pos; i < v.size(); i++) { if (t + v[i].l > v[i].t) continue; maxhappy = max(maxhappy, h + v[i].h); dfs(v, i + 1, t + v[i].l, h + v[i].h, maxhappy); } } int main() { int n; while (cin >> n) { if (n < 0) break; vector<bg> v; for (int i = 0; i < n; i++) { int h, l, t; cin >> h >> l >> t; v.push_back({h, l, t}); } sort(v.begin(), v.end(), compare); //排序,早结束的在前; //对于要参加的一系列bg,早结束的先参加,才能保证能参加的bg最多 int maxhappy = 0; dfs(v, 0, 0, 0, maxhappy); cout << maxhappy << endl; } }
#include <cstdio> #include <iostream> #include <vector> #include <map> using namespace std; struct bg{ int hp;int last;int lvTime;int staTime; bg(int h,int l,int lv){ hp=h;last=l;lvTime=lv;staTime=lv-last; } }; //对dfs结果进行备忘录 map<string,int> tagmap; //开始时间statime,活动bgs,当前已经选择了哪些活动choose;返回还能获得的开心值 int dfs(int statime,vector<bg> bgs,string choosed){ if(tagmap[choosed]!=0){ return tagmap[choosed]; } int hps=0; for(int i=0;i<bgs.size();i++){ if(statime<=bgs[i].staTime){ vector<bg> bgs2=bgs; bgs2[i].staTime=-1; string choosed2=choosed; choosed2[i]=1; hps=max(hps,bgs[i].hp+dfs(statime+bgs[i].last,bgs2,choosed2)); } } tagmap[choosed]=hps; return hps; } int main() { int n; while(scanf("%d",&n)!=-1){ if(n==-1){ break; } vector<bg> bgs; string choosed=""; for(int i=0;i<n;i++){ int h,l,lv; scanf("%d%d%d",&h,&l,&lv); bgs.push_back(bg(h,l,lv)); choosed+="0"; } tagmap.clear(); cout<<dfs(0,bgs,choosed)<<endl; } }
#include <iostream> #include <algorithm> using namespace std; int n,ans; struct Bg{ int score; int lasttime; int leavetime; }bg[31]; bool cmp(Bg a,Bg b){ return a.leavetime < b.leavetime; } void dfs1(int index,int sum,int score){ ans = max(ans,score); if(index >= n){ return; } if(bg[index].leavetime - sum < bg[index].lasttime){ dfs1(index+1,sum,score); }else{ dfs1(index+1,sum+bg[index].lasttime,score+bg[index].score); dfs1(index+1,sum,score); } } int main(){ while(cin >> n){ if(n == -1) break; for(int i = 0;i < n;i++) cin >> bg[i].score >> bg[i].lasttime >> bg[i].leavetime; ans = 0; sort(bg,bg+n,cmp); dfs1(0,0,0); cout << ans << endl; } }
#include <bits/stdc++.h> using namespace std; struct Node{ int h, l, ed; Node() {} Node(int _h, int _l, int _ed): h(_h), l(_l), ed(_ed) {} }; bool cmp(Node a, Node b){ if(a.ed != b.ed) return a.ed < b.ed; //先选最先结束的 else if(a.l != b.l) return a.l < b.l; //结束时间一样 选择时长最小的 else return a.h < b.h; //前两者均一样 选择快乐度最大的 } int ans; vector<Node> vn; void DFS(int index, int sum, int now){ //now指当前时刻 ans = max(ans, sum); if(index == vn.size()) return ; DFS(index+1, sum, now); //不选 if(now+vn[index].l <= vn[index].ed) DFS(index+1, sum+vn[index].h, now+vn[index].l); //选 } int main(){ int i, n, h, last, ed; while(~scanf("%d", &n) && n>=0){ vn.clear(); for(i=0; i<n; i++){ scanf("%d %d %d", &h, &last, &ed); vn.push_back(Node(h, last, ed)); } sort(vn.begin(), vn.end(), cmp); ans = 0; DFS(0, 0, 0); printf("%d\n", ans); } return 0; }总结:采用结构体形式存储信息,然后处理完输入信息后,要对输入的信息进行排序。排序规则见cmp。然后采用DFS版的0-1背包问题解决。(注意哦,这里如果不先对输入数据进行排序,直接使用背包法是解决不了的)
#include <bits/stdc++.h> using namespace std; struct bg { int lasttime,lefttime,happy; bg(int lastt=0,int left=0,int h=0):lasttime(lastt),lefttime(left),happy(h){} }; int enjoy(vector<bg> schedule,int tail,int sum,int time) { if(tail==schedule.size()) return sum; return max(enjoy(schedule,tail+1,sum,time),schedule[tail].lefttime>=time+schedule[tail].lasttime?enjoy(schedule,tail+1,sum+schedule[tail].happy,time+schedule[tail].lasttime):0); } int main() { int n; auto cmp=[](bg b1,bg b2){return b1.lefttime<b2.lefttime;}; while(cin>>n&&n!=-1) { vector<bg> schedule(n); for(auto &s:schedule) { int h,l,t; cin>>h>>l>>t; s=bg(l,t,h); } sort(schedule.begin(),schedule.end(),cmp); cout<<enjoy(schedule,0,0,0)<<endl; } return 0; }
#include<stdio.h> (737)#include<stdlib.h> typedef struct node { int h, l, t; }bg; int cmp(const void* a, const void* b) //按照离开时间降序 { return ((bg*)b)->t-((bg*)a)->t; } int ans = 0, n; bg ret[30]; void dfs(int k, int cur, int end) //k代表目前考虑的活动k,cur为目前的快乐值,end代表end之后的时间已经被安排了, //只能考虑0到end之间的的安排了 { if(k == n || end == 0) {if(cur > ans) ans = cur; return ;} dfs(k+1, cur, end); if(end <= ret[k].t && end-ret[k].l >= 0) //可以无空隙进行下一个活动 dfs(k+1, cur+ret[k].h, end-ret[k].l); else if(end > ret[k].t) //这里if必须加,因为前面的end-ret[k].l<0的情况不符合实际 dfs(k+1, cur+ret[k].h, ret[k].t-ret[k].l); //两个活动之间有空隙 return ; } int main() { while(scanf("%d", &n) != EOF && n != -1) { ans = 0; for(int i = 0; i < n; i++) scanf("%d %d %d", &ret[i].h, &ret[i].l, &ret[i].t); qsort(ret, n, sizeof(bg), cmp); dfs(0, 0, 1000); printf("%d\n", ans); } return 0; }
#include <iostream> (720)#include <cmath> #include <algorithm> using namespace std; struct BG{ int h; int l; int t; BG(){}; BG(int x, int y, int z):h(x),l(y),t(z){} }; const int MAXN = 30; int n; int ans = 0; BG bgArr[MAXN]; void dfs(int index, int sum, int times){ ans = max(sum, ans); if(index >= n){ return; } if(bgArr[index].t >= times + bgArr[index].l){ dfs(index+1, sum+bgArr[index].h, times + bgArr[index].l); } dfs(index+1, sum, times); } bool cmp(BG b1, BG b2){ return b1.t < b2.t; } int main() { while(cin >> n){ if(n == -1){ break; } ans = 0; for(int i = 0; i < n; i++){ int x, y, z; cin >> x >> y >> z; bgArr[i] = BG(x,y,z); } sort(bgArr, bgArr + n, cmp); dfs(0,0,0); cout<<ans<<endl; } return 0; }
#include <iostream> #include <algorithm> #include <cstring> using namespace std; struct BG{ int h,l,t; BG(){}; BG(int x,int y, int z):h(x),l(y),t(z){} }; const int MAXN = 30; BG data[MAXN]; int dp[1000]; bool cmp(BG b1, BG b2){ return b1.t < b2.t; } int main() { int n; while(cin >> n){ if(n == -1){ break; }; memset(dp, 0, sizeof(dp)); memset(data, 0, sizeof(data)); for(int i = 0; i < n; i++){ cin >> data[i].h >> data[i].l >> data[i].t; } sort(data, data + n, cmp); dp[0] = 0; int maxH = 0; for(int i = 0; i < n; i++){ for(int j = data[i].t; j >= data[i].l; j--){ dp[j] = max(dp[j], dp[j - data[i].l] + data[i].h); maxH = max(maxH, dp[j]); } } cout<<maxH<<endl; } return 0; }
#include<iostream> (720)#include<algorithm> #include<vector> /* 3 6 3 3 3 2 2 4 1 3 4 5 1 1 10 2 3 6 1 2 3 1 1 -1 according to the given data to output the max happy degree first sort limit time second dfs */ using namespace std; struct BG { int hd, sustain, limit; BG(int _hd = 0, int _sustain = 0, int _limit = 0) :hd(_hd), sustain(_sustain), limit(_limit) {} }; bool cmp(const BG &a, const BG &b) { return a.limit<b.limit; } int ans = 0; //bgs represent the bg data sort by limit time ascend //index represent the index of bgs array //attendtime represent the attend time of every dfs //sus represent the sum of happy degree of every dfs void dfs(vector<BG> bgs, int index,int attendTime,int sus) { ans = max(sus, ans); if (index == bgs.size())return ; //if the attendent time + sustain time <= bgs limit time //then continue dfs if (attendTime + bgs[index].sustain <= bgs[index].limit) dfs(bgs, index + 1, attendTime + bgs[index].sustain, bgs[index].hd + sus); dfs(bgs, index + 1,attendTime, sus); } int main() { int n; while (cin >> n && n > 0) { vector<BG> inp; for (int i = 0; i < n; i++) { int hp, sus, limi; cin >> hp >> sus >> limi; BG tmp (hp, sus, limi); inp.push_back(tmp); } //sort limit time ascend so that you can search every situation sort(inp.begin(), inp.end(),cmp); dfs(inp, 0, 0, 0); } }
//动态规划 #include<iostream> #include<algorithm> #include<stack> #include<queue> #include<string.h> #include<string> #include<stdio.h> #include<math.h> #include<map> #include<set> using namespace std; struct BG{ int h,l,t; bool operator<(const BG& r)const { if(t!=r.t) return t<r.t; return h<r.h; } }; BG bg[35]; int ht[2010]; int main() { int n; while(cin>>n) { memset(ht,0,sizeof(ht)); int all_ht=0; if(n<0) break; for(int i=0;i<n;i++) { cin>>bg[i].h>>bg[i].l>>bg[i].t; all_ht+=bg[i].t; } sort(bg,bg+n); for(int i=0;i<n;i++) { for(int j=bg[i].t;j>=bg[i].l;j--) if(ht[j]<ht[j-bg[i].l]+bg[i].h) { ht[j]=ht[j-bg[i].l]+bg[i].h; } } int ans=0; for(int i=1;i<=all_ht;i++) if(ht[i]>ans) ans=ht[i]; printf("%d\n",ans); } }
//取个巧,因为本题n比较小(只有30)所以递归也不会超时,正常地还是用动态规划做吧。
}