11284: 【原1284】背包

题目

题目描述

author: Cheezer 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1284

Description

话说在大三ACM班K个人即将从美帝回归祖国的怀抱之时，他们有N种物品想带回来，每种物品有给定的体积和价值，但每个人都只能带总体积为V的物品。

在他们眼中，合理的方案应该是这样的：

每个人带了恰好总体积为V的物品
每个人对于同种物品最多带一件，但不同的人可以带同一种物品
任意两个人，带的物品不能完全相同

他们想知道满足以上条件的方案中所有人带的物品的总价值最大是多少。

Input Format

第一行三个数K, V, N。

第二行起的N行，每行两个数，表示每个物品的体积和价值。

30%的数据：\( 1 \le K \le 10, 1 \le N \le 100 \)

100%的数据：\( K \le 50, V \le 5000, N \le 200 \)，单件物品的体积和价值不超过5000。

Output Format

一行，即所求最大价值。

Sample Input

Sample Output

Sample Illustration

第一个人选择体积为7,2,1的三种物品，价值为25。第二个人选择体积为3,7的两种物品，价值为32。总价值为57。

WashSwang's solution

#include <iostream>
#include <cstring>
using namespace std;
int f[51][5001],a[51],b[51],n,k,v,w,c,pa,pb,ans;
int main() {
    scanf("%d%d%d",&k,&v,&n);
    memset(f,0x80,sizeof(f));
    f[0][0]=0;
    for (int i=0;i<n;++i){
        scanf("%d%d",&w,&c);
        for (int j=v;j>=w;--j){
            for (int l=0;l<k;++l){
                a[l]=f[l][j];
                b[l]=f[l][j-w]+c;
            }
            pa=pb=0;
            for (int l=0;l<k;++l)
                if (a[pa]>b[pb]) f[l][j]=a[pa++];
                else f[l][j]=b[pb++];
        }
    }
    for (int i=0;i<k;++i) ans+=f[i][v];
    printf("%d",ans);
    return 0;
}