首页 > 代码库 > [Jobdu] 题目1455:珍惜现在,感恩生活
[Jobdu] 题目1455:珍惜现在,感恩生活
- 题目描述:
为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买。请问:你用有限的资金最多能采购多少公斤粮食呢?
- 输入:
输入数据首先包含一个正整数C,表示有C组测试用例,每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类,然后是m行数据,每行包含3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20),分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
- 输出:
对于每组测试数据,请输出能够购买大米的最多重量,你可以假设经费买不光所有的大米,并且经费你可以不用完。每个实例的输出占一行。
- 样例输入:
18 22 100 44 100 2
- 样例输出:
400
经典的背包问题,动态规划。
1 #include <iostream> 2 using namespace std; 3 4 int C; 5 int n, m; 6 int p, h, c; 7 int dp[101]; 8 int res; 9 10 int max(int a, int b) {11 return a > b ? a : b;12 }13 14 void init() {15 res = 0;16 for (int i = 0; i < n + 1; ++i) {17 dp[i] = -1;18 }19 dp[0] = 0;20 }21 22 void refresh() {23 for (int i = 0; i < c; ++i) {24 for (int j = n; j >= p; --j) {25 if (dp[j-p] >= 0) {26 dp[j] = max(dp[j], dp[j-p] + h);27 }28 res = max(res, dp[j]);29 }30 }31 }32 33 int main() {34 cin >> C;35 for (int i = 0; i < C; ++i) {36 init();37 cin >> n >> m;38 for (int j = 0; j < m; ++j) {39 cin >> p >> h >> c;40 refresh();41 }42 cout << res << endl;43 }44 return 0;45 }46 /**************************************************************47 Problem: 145548 User: hupo25049 Language: C++50 Result: Accepted51 Time:10 ms52 Memory:1520 kb53 ****************************************************************/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。