#include <bits/stdc++.h> using namespace std; const int inf = 5000005; int n, m, t, price[105][105], f[10005]; int main(void) { ios::sync_with_stdio(false); cin >> t >> n >> m; for (int i = 1; i <= t; i++) { for (int j = 1; j <= n; j++) { cin >> price[j][i]; } } for (int k = 1; k < t; k++) { memset(f, 0, sizeof f); for (int i = 1; i <= n; i++) { for (int j = price[i][k]; j <= m; j++) { f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]); } } m += f[m]; } cout << m << endl; return 0; }

这是一道完全背包的题，我们进行 t−1 轮完全背包: 把今天手里的钱当做背包的容量， 把商品今天的价格当成它的消耗, 把商品明天的价格当做它的价值， 每一天结束后把总钱数加上今天赚的钱，直接写背包模板即可。 另： 在这道题中，我们可以把商品和钱看成同样的东西，因为题目中说了：可以当天买当天卖，所以不必考虑跨天的买卖，只需考虑当天的即可，这满足动态规划对于最优化原理和无后效性的要求，可以大胆地购买。

#include<bits/stdc++.h> using namespace std; const int N = 110, M = 1e4 + 10; int w[N][N]; // w[t][i]：第 t 天第 i 种物品的价格 int dp[M]; // dp[j]：背包容量为 j 时的最大价值 int main() { }

#include <bits/stdc++.h> using namespace std; const int inf = 5000005; int n, m, t, price[105][105], f[10005]; int main(void){ //ios::sync_with_stdio(false); cin >> t >> n >> m; for (int i = 1; i <= t; i++){ for (int j = 1; j <= n; j++){ cin >> price[j][i]; } } for (int k = 1; k < t; k++){ memset(f, 0, sizeof f); for (int i = 1; i <= n; i++){ for (int j = price[i][k]; j <= m; j++){ f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]); } } m += f[m]; } cout << m << endl; return 0; }

#include <iostream> #include <cstring> #include <algorithm> using namespace std; int a[10005]; int w[105][105]; int main() { int T,N,M; cin>>T>>N>>M; for (int i=1;i<=T;i++) { for (int j=1;j<=N;j++) { cin>>w[i][j]; } } for (int t=1;t<=T;t++) { memset(a,0,sizeof(a)); for (int i=1;i<=N;i++) { for (int j=w[t][i];j<=M;j++) { a[j]=max(a[j],a[j-w[t][i]]+(w[t+1][i]-w[t][i])); } } M+=a[M]; } cout<<M; return 0; }

#include<bits/stdc++.h> using namespace std; int t,n,m;//t天，n件，m个 int a[105][105],dp[105],g[10005]; int main(){ cin>>t>>n>>m; for(int i=1;i<=t;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; dp[1]=m; for(int i=2;i<=t;i++){ memset(g,0,sizeof(g)); for(int j=1;j<=dp[i-1];j++){ g[j]=max(g[j],j); for(int k=1;k<=n;k++) if(j-a[i-1][k]>=0) g[j]=max(g[j],g[j-a[i-1][k]]+a[i][k]); } dp[i]=max(dp[i-1],g[dp[i-1]]); } cout<<dp[t]; return 0; }

#include<bits/stdc++.h> using namespace std; int t,n,m; int a[105][105],dp[105],g[10005]; int main(){ cin>>t>>n>>m; for(int i=1;i<=t;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } dp[1]=m; for(int i=2;i<=t;i++){ memset(g,0,sizeof(g)); for(int j=1;j<=dp[i-1];j++){ g[j]=max(g[j],j); for(int k=1;k<=n;k++){ if(j-a[i-1][k]>=0) g[j]=max(g[j],g[j-a[i-1][k]]+a[i][k]); } } dp[i]=max(dp[i-1],g[dp[i-1]]); } cout<<dp[t]; return 0; }