题目大意
洛谷 P1855 榨取kkksc03
多维背包模板题。
给定 \(n\) 个愿望，第 \(i\) 个愿望所需金钱为 \(m_i\)，所需时间为 \(t_i\)。现在 kkksc03 有 \(M\) 块钱，暑假时间为 \(T\)，问在暑假期间他最多能满足多少个愿望。
思路分析
由于其除了增加一维外，其余底层逻辑为 0-1 背包类似，所以可以在 0-1 背包的基础上修改。
0-1 背包状态转移方程，其中 \(v_i\) 为体积，\(w_i\) 为价值。
\[dp_j=\max(dp_j,dp_{j-v_i}+w_i)
\]
多维背包状态转移方程，其中把物品数量 \(1\) 作为价值。
\[dp_{j\color{red}{,k}}=\max(dp_{j\color{red}{,k}},dp_{j\color{red}{-m_i,k-t_i}}{\color{red}{+1}})
\]
代码呈现
#include<bits/stdc++.h>
using namespace std;const int N=105,maxM=205;
int n,M,T;
int m[N],t[N],dp[maxM][maxM];int main(){scanf("%d%d%d",&n,&M,&T);for (int i=1;i<=n;++i) scanf("%d%d",m+i,t+i);for (int i=1;i<=n;++i){for (int j=M;j>=m[i];--j){for (int k=T;k>=t[i];--k) dp[j][k]=max(dp[j][k],dp[j-m[i]][k-t[i]]+1);}}printf("%d",dp[M][T]);return 0;
}