【t060】可怜的波特
2024-08-31 20:22:13
Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
哈里波特在姨夫家遭受非人待遇,他被迫做很多事。有一次,姨夫有给了他一大堆家务。哈里知道每件做完家务的时间,重要程度,
还知道总时间与任务总数,他必须尽量合理的安排使他在规定时间内完成的重要程度最大。
【输入格式】
第一行,t,m(t,m<=10000)表示哈里波特的时间和姨夫要他做的家务数。
接下来m行,每行2个值表示该任务所须的时间与重要度(均小于5000)。
【输出格式】
一行di表示完成的任务重要数总和。
Sample Input
70 3
71 100
69 1
1 2
Sample Output
3
【题解】
还能有更裸的0/1背包吗?逆序枚举时间。最后输出f[m]。做得我要吐血了。
【代码】
#include <cstdio> int m,n,w[10010],c[10010],f[10010]; int main()
{
//freopen("F:\\rush.txt","r",stdin);
scanf("%d%d",&m,&n); //输入时间上限和物品个数
for (int i = 1;i <= n;i++) //输入n个物品的信息
scanf("%d%d",&w[i],&c[i]);
for (int i = 1;i <= n;i++) //进行0/1背包操作
for (int j = m;j >= w[i];j--)
if(f[j] < f[j-w[i]] + c[i])
f[j] = f[j-w[i]] + c[i];
printf("%d",f[m]); //最后输出所用时间不超过m的最大价值度
return 0;
}
最新文章
- Swift利用协议优化NSNotificationCenter
- winform中button的image属性无法更改
- struts2请求的URL的搜索路径的顺序概述
- 玩转WIN7的MKLINK
- nc 反弹链接
- CSS 编码规范
- 编写2个接口:InterfaceA和InterfaceB;在接口InterfaceA中有个方法void printCapitalLetter();在接口InterfaceB中有个方法void printLowercaseLetter();然 后写一个类Print实现接口InterfaceA和InterfaceB,最后再在主类E 的main方法中创建Print的对象并赋值,运行方法
- HttpContext及HttpContext.current
- CentOS安装Node.js简单教程
- mysql中DES加密解密
- 字符串对比.net String.EndsWith方法 (String)
- JAVA基础:自己构造一个按递增排列的数组,用户输入一个数,插入适当位置
- 人工智能二:TensorFlow环境搭建
- PHP保留两位小数并且四舍五入及不四舍五入的方法
- 个人博客地址: furur.xyz
- vue 父组件给子组件传值 Vue父组件给子组件传方法 Vue父组件把整个实例传给子组件
- jquery扩展的两个方法与区别 $.extend $.fn.extend
- (转)mmap和shm共享内存的区别和联系
- 单纯形算法 matlab
- HAproxy.md