原題鏈接
此題是01背包的變形，與傳統01背包不同的是每件物品貢獻的計算方式

如果在 \(t\) 時刻完成第 \(i\) 樣食材則得到 \(a_i - t × b_i\) 的美味指數

這句話意味著食材的美味指數在不同的時間有著不一樣的數值，也就是說，烹調的先后順序會影響得到的美味指數
假設有兩樣食材 \(i,j\)
\(a_i = 1,b_i = 0,c_i = 1\)
\(a_j = 1,b_j = 1,c_j = 1\)
假設從 \(0\) 時刻開始烹調：
先烹調 \(i\) 再烹調 \(j\) 得到的美味指數：

$a_j-(c_i+c_j)×b_j+a_i-c_i×b_i=0$ 先烹調 $j$ 再烹調 $i$ 得到的美味指數： $a_i-(c_j+c_i)×b_i+a_j-c_j×b_j=1$ 我們希望食材烹調的順序能保證我們找到最優解，即先烹調位于數組前面的食材所得到的美味指數必定大于先烹調位于數組后面的食材所得到的美味指數，假設 $i$ 在 $j$ 前面，那么就要保證： $a_j-(c_i+c_j)×b_j+a_i-c_i×b_i>a_i-(c_j+c_i)×b_i+a_j-c_j×b_j$ 即 $c_j×b_i>c_i×b_j$ 所以我們可以將食材按照上式進行排序，這樣就可以保證整體的最優解了

AC代碼：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
struct node{
	ll a,b,c;
}s[55];
bool cmp(node n1,node n2){
	return n2.c * n1.b > n1.c * n2.b;
}
ll dp[N];
int main(){
	ll t,n,ans = 0;
	cin>>t>>n;
	for(int i=1;i<=n;i++) cin>>s[i].a;
	for(int i=1;i<=n;i++) cin>>s[i].b;
	for(int i=1;i<=n;i++) cin>>s[i].c;
	sort(s + 1,s + n + 1,cmp);
	for(int i=1;i<=n;i++){
		for(int j=t;j>=s[i].c;j--){
			dp[j] = max(dp[j],dp[j - s[i].c] + s[i].a - j * s[i].b);
			ans = max(ans,dp[j]);
		}
	}
	cout<<ans;
	return 0;
}