【題目描述：】

...?（宣傳luogu2的內容被自動省略）

洛谷的運營組決定，如果...，那么他可以浪費掉kkksc03的一些時間的同時消耗掉kkksc03的一些金錢以滿足自己的一個愿望。

Kkksc03的時間和金錢是有限的，所以他很難滿足所有同學的愿望。所以他想知道在自己的能力范圍內，最多可以完成多少同學的愿望？

【輸入格式：】

第一行,n M T，表示一共有n(n<=100)個愿望，kkksc03 的手上還剩M(M<=200)元，他的暑假有T(T<=200)分鐘時間。

第2~n+1行 mi,ti 表示第i個愿望所需要的時間和金錢。

【輸出格式：】

一行，一個數，表示kkksc03最多可以實現愿望的個數。

?

[算法分析：]

乍一看題目，誒？怎么這么像01背包？

啊！好像就是01背包，只不過同時有了兩個限制條件.

這樣DP方程就很容易得出了：

　　f[j][k] = max(f[j][k], f[j - m[i]][k - t[i]] + 1)

　　1≤i≤n, ?m[i]≤j≤M, ?t[i]≤k≤T

?

[Code:]

1 //榨取kkksc03 2 #include<iostream> 3 #include<cstdio> 4 using namespace std; 5 6 const int MAXN = 100 + 1; 7 const int MAXM = 200 + 1; 8 9 int n, M, T; 10 int m[MAXN], t[MAXN]; 11 int f[MAXM][MAXM]; 12 13 int main() { 14 scanf("%d%d%d", &n, &M, &T); 15 for(int i=1; i<=n; ++i) 16 scanf("%d%d", &m[i], &t[i]); 17 for(int i=1; i<=n; ++i) 18 for(int j=M; j>=m[i]; --j) 19 for(int k=T; k>=t[i]; --k) { 20 f[j][k] = max(f[j][k], f[j - m[i]][k - t[i]] + 1); 21 } 22 printf("%d\n", f[M][T]); 23 }

?

轉載于:https://www.cnblogs.com/devilk-sjj/p/9066184.html

總結

以上是生活随笔為你收集整理的【洛谷】【动态规划/二维背包】P1855 榨取kkksc03的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。