ACboy needs your help-分组背包模板题
2024-09-28 06:34:24
Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
Description
ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the
profit?
profit?
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.
Output
For each data set, your program should output a line which contains the number of the max profit ACboy will gain.
Sample Input
2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
Sample Output
3
4
6
/*
Author: 2486
Memory: 1456 KB Time: 93 MS
Language: G++ Result: Accepted
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn=100+5;
int dp[maxn],a[maxn][maxn];
int n,m;
int main() {
while(~scanf("%d%d",&n,&m),n&&m) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
scanf("%d",&a[i][j]);
}
}
memset(dp,0,sizeof(dp));
int Max=0;
for(int i=1; i<=n; i++) {
for(int k=m; k>=0; k--) {
for(int j=1; j<=m; j++) {
if(k-j<0)break;
dp[k]=max(dp[k],dp[k-j]+a[i][j]);
}
}
}
printf("%d\n",dp[m]);
}
return 0;
}
最新文章
- SharePoint Online 申请试用链接地址
- c++ 基础一
- ssh(sturts2_spring_hibernate) 框架搭建之struts2
- 安装DELL R430服务器的过程记录
- [SoapUI] 同一个Resource不同参数时,在两个step里默认打开总是同一个Resource
- char 转wchar_t 及wchar_t转char
- 一次ssl的手动实现——加密算法的简单扫荡
- css的一些小技巧!页面视觉差!
- vs vim 插件
- POJ 2524
- POJ1811 Prime Test(miller素数判断&;&;pollar_rho大数分解)
- 输出流 写文件 文本 换行nextLine
- 在IIS Express中调试时无法读取配置文件
- node-webkit学习之【无边框窗口用JS实现拖动改变大小等】
- sql 存储过程和触发器
- navicate 远程无法链接linux上mysql数据库问题
- nodejs 数据库操作,消息的发送和接收,模拟同步
- python 数字格式化
- JS之滚动条效果2
- 01-学前入门.Net 能做什么
热门文章
- Swift, Playgrounds, and XCPlayground
- 【Shell 编程基础第一部分】第一个Shell脚本HelloShell及一些简单的Shell基础书写与概念;
- sprintf,snprintf的用法(可以作为linux中itoa函数的补充)【转】
- 使用pipeline管道执行redis命令
- foreach 与 Linq的 Select 效率问题
- OSSIM 4 组件目录
- Codeforces 810 B. Summer sell-off
- [BZOJ1790][AHOI2008]Rectangle 矩形藏宝地(四维偏序,CDQ+线段树)
- Ze_Min Tree 主席树
- [UOJ182]a^-1 + b problem