【分组背包】洛谷P1757 通天之分组背包

题目传送门

实现伪代码:

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

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

代码实现:

#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;
}
点赞

发表评论