每个输入包含一个测试用例。
输入的第一行包括两个正整数,表示股票的种数N(1<=N<=1000)和牛牛借的钱数M(1<=M<=1000)。
接下来N行,每行包含两个正整数,表示这只股票每一股的买入价X(1<=X<=1000)和卖出价Y(1<=Y<=2000)。
每只股票可以买入多股,但必须是整数。
输出一个整数表示牛牛最多能赚的钱数。
3 5 3 6 2 3 1 1
4
#include <iostream>#include <vector>usingnamespacestd;intmain(){vector<int> cost;vector<int> profit;intN, M;while(cin>>N>>M){for(inti = 0; i < N; i++){intin, out;cin>>in>>out;cost.push_back(in);profit.push_back(out - in);}vector<vector<int>> maxprofit(N, vector<int>(M + 1, 0));for(inti = 0; i < N; i++){maxprofit[i][0] = 0;}for(intj = 1; j <= M; j++){if(j >= cost[0]){maxprofit[0][j] = maxprofit[0][j - cost[0]] + profit[0];}}for(inti = 1; i < N; i++){for(intj = 0; j <= M; j++){maxprofit[i][j] = maxprofit[i - 1][j];if(j >= cost[i] && maxprofit[i][j - cost[i]] + profit[i] > maxprofit[i][j])maxprofit[i][j] = maxprofit[i][j - cost[i]] + profit[i];}}if(maxprofit[N - 1][M] >= 0)cout<<maxprofit[N - 1][M]<<endl;elsecout<<0<<endl;cost.clear();profit.clear();}return0;}