首页 > 代码库 > 【hdu1712】分组背包（每组最多选1个）
【hdu1712】分组背包（每组最多选1个）
【分组背包】
【题意】ACboy要开始选课了，上一门课能够获得的收益和他上这门课的时间是有关的，然后给你若干门课，让你帮他进行选课，
每一门课自然是只能选择一个课程时长，问你如何选择，才能使ACboy获得的受益最大。
for(k=1;k<=K;k++)
for(int v=V;v>=0;v--)
for(int i=item in group k)
f[v]=max(f[v],f[v-c[i]+w[i]);
保证用到的都是k-1所更新的而不是k所更新的。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 #include<queue>
7 #include<vector>
8 using namespace std;
9
10 const int N=110;
11 int n,m,a[N][N],f[N];
12
13 int maxx(int x,int y){return x>y ? x:y;}
14
15 int main()
16 {
17 freopen("a.in","r",stdin);
18 while(1)
19 {
20 scanf("%d%d",&n,&m);
21 if(!n && !m) return 0;
22 for(int i=1;i<=n;i++)
23 for(int j=1;j<=m;j++)
24 {
25 scanf("%d",&a[i][j]);
26 }
27 memset(f,0,sizeof(f));
28 for(int i=1;i<=n;i++)
29 for(int j=m;j>=1;j--)
30 for(int k=1;k<=j;k++)
31 {
32 f[j]=maxx(f[j],f[j-k]+a[i][k]);
33 }
34 printf("%d\n",f[m]);
35 }
36 return 0;
37 }
【hdu1712】分组背包（每组最多选1个）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。