书海扬帆的博客

题目传送门

实现伪代码:

1
2
3
4
for 所有的组k
for v=V..0
for 所有的i属于组k
      f[v]=max{f[v],f[v-w[i]]+c[i]}

第一次写分组背包,继续加油吧~

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
const int maxn=1010;
int n,m;
int dp[maxn],a[maxn],b[maxn],c[105][1010],p[105],cnt,opt;
int main() {
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++) {
scanf("%d%d%d",&a[i],&b[i],&opt);
cnt=max(cnt,opt);
c[opt][++p[opt]]=i;
}
for(int i=1;i<=cnt;i++) {
for(int j=m;j>=0;j--) {
for(int k=1;k<=p[i];k++) {
if(j>=a[c[i][k]])
dp[j]=max(dp[j],dp[j-a[c[i][k]]]+b[c[i][k]]);
}
}
}
printf("%d\n",dp[m]);
return 0;
}

 评论



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k