734. Energy stone (greed, backpack)

An energy stone has its own l,e,s, You can think of 01 knapsack problem , because 01 Knapsack is linear recursive , Think about whether there is one Sort Methods , It can make us greedy to get the most energy ？

You can think of the adjacent term exchange method , By exchanging two energy stones , See if you can launch relational  

 

  As shown in the figure, we can get the relationship , Get the last order , Make one 01 A backpack will do

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=105;
const int M=1e4+10;
int dp[M];
struct node
{
    int s;  // Spend time 
    int e;  // energy 
    int l;  // Energy loss 
    bool operator<(const node b)const
    {
        return b.l*s<l*b.s;
    }
}a[N];

void solve(int g)
{
    int n;
    int m=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].s>>a[i].e>>a[i].l,m+=a[i].s;
    
    sort(a+1,a+1+n);
    memset(dp,-0x3f,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i].s;j--)
            dp[j]=max(dp[j],dp[j-a[i].s]+max(0,a[i].e-(j-a[i].s)*a[i].l));
    int res=0;
    for(int i=0;i<=m;i++)
        res=max(res,dp[i]);
    printf("Case #%d: %d\n",g,res);
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
        solve(i);
    return 0;
}