庆功会题目链接

1019. 庆功会 - AcWing题库

庆功会题目类型

多重背包问题模板

庆功会题目解析

动态规划

• 状态表示f[i,j]
  • 集合：所有只从前i个物品中选，并且总体积不超过j的选法
  • 属性：Max
• 状态计算
  • f[i] [j] = Max(f[i - 1] [j - v[i] * k] + w[i] * k); k = 0, 1, 2, ..., s[i]

庆功会代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510;
const int M = 6010;

int n,m;
int f[N][M],v[N],w[N],s[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d %d %d",&v[i],&w[i],&s[i]);
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=m;++j)
        {
            for(int k=0;k<=s[i]&&k*v[i]<=j;++k)
            {
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
            }
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}

一维优化版

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510;
const int M = 6010;

int n,m;
int f[M],v[N],w[N],s[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)
    {
        scanf("%d %d %d",&v[i],&w[i],&s[i]);
    }
    for(int i=0;i<n;++i)
    {
        for(int j=m;j>=0;--j)
        {
            for(int k=0;k<=s[i]&&k*v[i]<=j;++k)
            {
                f[j]=max(f[j],f[j-k*v[i]]+w[i]*k);
            }
        }
    }
    printf("%d\n",f[m]);
    return 0;
}