Problem Description

多组输入。

对于每组输入,第一行有两个整数N,X(1 < = N < = 100,1 < = X < = 1000),分别表示哈士奇的数量和高数巨的钱数

对于每组数据,输出一个整数,表示高数巨最多可以获得的萌值,每组输出占一行

Example Input
2 100 50 20 60 40 3 100 20 55 20 35 90 95 1 10 20 50
Example Output
40 95 0
Hint

 

上午学长刚讲的背包问题, 属于01背包

关键代码

for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};

01 #include<stdio.h>
02 #include<string.h>
03 int max(int a, int b);
04 int main()
05 {
06     int n, x, p[111], m[111], j, i;
07     int a[1005];
08     while(scanf("%d%d", &n, &x) != EOF)
09     {
10         memset(a, 0, sizeof(a));
11         memset(p, 0, sizeof(p));
12         memset(m, 0, sizeof(m));
13         for(i = 1; i <= n; i++)
14             scanf("%d%d", &p[i], &m[i]);
15         for(i = 1; i <= n; i++)
16         {
17             for(j = x; j >= 0; j--)
18                 if(j >= p[i])
19                     a[j] = max(a[j], a[j - p[i]] + m[i]);
20         }
21         printf("%d\n", a[x]);
22     }
23     return 0;
24 }
25 int max(int a, int b)
26 {
27     return a > b? a : b;
28 }
29  

技术
©2020 ioDraw All rights reserved
在上海做什么赚钱快?这10个你可以试一试!PHP 先返回结果到前端,PHP代码继续执行后续的任务centos7部署springboot jar包 疫情过后 学哪个编程有前景安卓开发—根据顾客预算显示食物信息苹果iPhone 12全系售价泄露:官方最高售价近1万元log4j打印异常堆栈信息的方法PTA快速排序日经:索尼和铠侠正积极申请华为供货许可一个学生关于鸿蒙系统的一些看法