毕业bg

/* 这道题在第一眼看的时候，觉得应该用贪心算法，但说实话个人觉得贪心算法就好像打赌一样
，这种五五开的算法个人不是很敢用。
因此我开始尝试其他解法。首先想到的就枚举，但是枚举太耗时。转念一想，暴力枚举的另一种表现
形式那毫无疑问就是搜索了，因此这道题可以考虑用搜索策略来解决
单纯的搜索肯定会超时，因此这道题还需要进行剪枝。剪枝的依据就是根据参加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));
        }
    }
}

/*最开始想到贪心，但此题不能用贪心！！以下是我的思考过程，可能细节上还有点毛病
  
  关于贪心的使用————每个阶段的最优状态都是由上一个阶段的最优状态得到的
  那么该问题的状态和阶段是什么呢？
  现在来看关于阶段的定义，所谓阶段是指随着问题的解决，在同一个时刻可能会
  得到的不同状态的集合。我们可以把时间作为划分阶段的尺度，那么就是第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;
}

	#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 <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 <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）所以递归也不会超时，正常地还是用动态规划做吧。

}