[动态规划][背包问题][P1156 垃圾陷阱]做题思路和总结

背包问题][P1156 垃圾陷阱]做题思路和总结"/>

[动态规划][背包问题][P1156 垃圾陷阱]做题思路和总结

题目描述

卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D(2≤D≤100)英尺。

卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间t(0<t≤1000)，以及每个垃圾堆放的高度h(1≤h≤25)和吃进该垃圾能维持生命的时间f(1≤f≤30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。

思路

    其实不难发现，通过阅读题面可以发现背包问题的气息（垃圾可以通过排序，将高度作为背包容量，补充的能量为价值），用DP[i][j]表示考虑前i个垃圾，垃圾高度为j的时候，奶牛可以得到的最大能量，如果在某一次DP运算的时候最大能量不小于0（等于0的时候，奶牛可以在濒死状态下进行操作）的时候，j>=D的时候就可以逃出陷阱。如果找不到，接下来遍历寻找最大存活时间。

    显然DP[0][0] = 10.这是最初的状态；

    DP数组最初应该初始化为-INF,0为濒死状态，应该考虑进运算。

    进行状态转移运算的时候要考虑奶牛能量的损耗（这就是存在代码(Rubbish[i].T-Rubbish[i-1].T)的原因）

    当找不到逃出方案的时候，寻找最长存活时间，应该从DP数组遍历（某一种状态的能量最大值加上垃圾出现的时间），不断获取最大值。

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;struct _Rubbish
{int T;int H;int F;
}Rubbish[1001];int D,G;
int INF = 0XFFFFF;
int DP[101][1001] = {0};bool cmp(_Rubbish,_Rubbish);int main(void)
{cin >> D >> G;for(int i = 1;i <= G;i++){cin >> Rubbish[i].T >> Rubbish[i].F >> Rubbish[i].H;}sort(Rubbish+1,Rubbish+G+1,cmp);for(int i = 0;i <= G;i++){for(int j = 0;j <= D;j++){DP[i][j] = -INF;}}DP[0][0] = 10;Rubbish[0].T = Rubbish[0].F = Rubbish[0].H = 0;for(int i = 1;i <= G;i++){for(int j = 0;j <= D;j++){//Eat or non-Eat//濒死状态（Life == 0）的时候也可以吃if(DP[i-1][j]-(Rubbish[i].T-Rubbish[i-1].T) >= 0){DP[i][j] = max(DP[i][j],DP[i-1][j]+Rubbish[i].F-(Rubbish[i].T-Rubbish[i-1].T));}if(j-Rubbish[i].H >= 0 && DP[i-1][j-Rubbish[i].H]-(Rubbish[i].T-Rubbish[i-1].T) >= 0){DP[i][j] = max(DP[i][j],DP[i-1][j-Rubbish[i].H]-(Rubbish[i].T-Rubbish[i-1].T));if(j >= D){cout << Rubbish[i].T << endl;return 0;}}}}int ans = 0;for(int i = 0;i <= G;i++){for(int j = 0;j <= D;j++){if(DP[i][j] != - INF){ans = max(ans,DP[i][j]+Rubbish[i].T);}}}cout << ans << endl;return 0;
}bool cmp(_Rubbish a,_Rubbish b)
{return a.T < b.T;
}