题目描述

西西艾弗岛上共有 n 间物流仓库，小 P 目前有 m 件货物存放其中。为了获得至少为 v 的现金，小 P 需要选取一些货物卖出。

已知货物信息如下，第 i 件（0≤i<m）货物：

• 存放在第 ti​ 间仓库中（0≤ti​<n）；

• 价值为 ai​，即选择卖出该货物可获得 ai​ 的现金。

但在调货出库时也需要支付一些费用，对于第 j 间（0≤j<n）仓库：

• 只要调用了该仓库的货物（至少一件），就需要支付 bj​ 的基本费用；

• 如果调用了该仓库中共 kk 件货物，则还需要支付 k×cj​ 的计件费用。

小 P 的最终目标是获得至少为 v 的现金，即要求卖出的货物总价值减去总费用的结果大于或等于 v。 在满足该目标的前提下，试为小 P 规划一种花费最小的卖货方案。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 n、m 和 v。

接下来 n 行输入仓库信息，其中第 j 行（0≤j<n）包含两个整数 bj​ 和 cj​。

接下来 m 行输入货物信息，其中第 i 行（0≤i<m）包含两个整数 ai​ 和 ti​。

输出格式

输出到标准输出。

仅输出一个整数，表示完成目标前提下的最小花费。

样例1输入

2 3 15
2 1
3 2
10 0
20 1
15 0

样例1输出

4

样例1解释

最优方案：选取货物 0 和 2，二者均在 0 号仓库，总花费为 2+2×1=4。

选取货物 1 也刚好能满足要求（20−3−1×2≥15），但花费更多。

单独选取货物 0 或 2 均不能满足要求。

样例2输入

5 3 15
2 1
1 1
3 2
4 2
1 5
10 1
10 1
10 1

样例2输出

3

样例2解释

小 P 所有货物均存放在仓库 1 中，任取两件货物卖出即可满足要求（10+10−1−2×1≥15）。

子任务

30% 的数据满足：

• m≤15

另有 40%40% 的数据满足：

• ai​≤20

全部的数据满足：

• 0<n,m≤1000

• 0<bj​,cj​≤20

• 0<ai​≤1000

• 0<v≤106 且保证至少存在一种可满足要求的卖货方案。

题解

思路

把“收益−费用≥v”转成“净收益≥0”，把每件货的价值当正数、把仓库首次调用的基本费bj和k件计件费k×cj当负数，净收益=总价值−总费用−v；随后按仓库分组、组内按价值降序，逆序跑分组背包：f[k]表示净收益为k时的最小总费用，最终f[v]即为满足净收益≥0的最小总开销。

这是一道分组背包问题，但与常规分组背包相比，需要针对以下两个特殊情况进行处理：

1. 组内物品的选择需要采用贪心策略。由于相同购买数量的物品价格固定，我们应优先选择价值最高的物品，这样可以直接计算出每组物品的最佳价格和价值组合。

2. 需要考虑溢价情况（即卖出金额超过目标金额）。处理方法是当数组下标为负时，将其值设为0即可。

分组背包内部按照0-1背包做，然后按分组背包的模版做即可。

0-1背包模版

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}

分组背包模版

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int temp;
        cin>>temp;
        b[i]=temp;
        for(int j=1;j<=temp;j++){
            cin>>a[i][j]>>c[i][j];
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
            for(int k=0;k<=b[i];k++)
                if(j>=a[i][k])
                    f[j]=max(f[j],f[j-a[i][k]]+c[i][k]);
    cout<<f[m];
}

实现细节

每组物品的价值可以在循环内部计算，使用两个变量，每次在循环内部累加即可。

背包容量需初始化为无穷大。

具体过程

变量

• n, m, v 分别表示角色数量、物品数量和背包容量上限。
• p[id] 存储每个角色拥有的物品价值，va[id] 存储对应物品的代价。
• b[i] 是角色 i 的启动费，c[i] 是追加物品的额外费。

输入阶段先读取所有角色的启动费和追加费，再逐个处理物品：

• 每个物品的价值 x 和所属角色 id 被存入 p[id]。
• 若物品是角色的第一个物品，代价为启动费加追加费；否则仅需追加费。

动态规划初始化

• f[k] 表示总价值达到 k 时的最小代价，初始化为无穷大（不可达状态）。
• 基础状态 f[0] = 0 表示零价值无需代价，同时当id小于0的时候 f[id] = 0。

预处理排序

对每个角色的物品按价值降序排序。这一操作确保后续动态规划中优先选择高价值物品，以优化背包填充效率。

分组背包动态规划

核心逻辑分为三层循环：

1. 外层循环枚举角色（组）：处理每个角色的物品集合。
2. 中层逆序枚举背包容量：从 v 到 0 保证每个物品只被选一次。
3. 内层枚举当前角色选多少个物品：
   • 累计所选物品的总价值 value 和总代价 cost。
   • 若剩余容量 k 能覆盖净消耗（value - cost），则更新状态：
   • 否则直接支付当前累计代价 cost 并更新状态。

输出结果

最终 f[v] 即为总价值不超过 v 的最小代价，直接输出该值。

代码

有注释

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;      // 最大角色数
const int M = 1e6 + 10;  // 最大背包容量（价值上界）

int n, m, v;             // n 个角色，m 个物品，背包容量 v
vector<int> p[N];        // p[id] 存放角色 id 的所有物品价值
vector<int> va[N];       // va[id][j] 表示选该角色第 j 个物品时的代价
int b[N], c[N];          // b[i] 启动费，c[i] 每追加一个物品的额外费
int f[M];                // f[k] = 总价值为 k 时的最小总代价

int main() {
    cin >> n >> m >> v;
    for (int i = 0; i < n; i++) cin >> b[i] >> c[i];

    /* ---------- 读入 m 个物品 ---------- */
    for (int i = 1; i <= m; i++) {
        int x, id;               // x 价值，id 所属角色
        cin >> x >> id;
        p[id].push_back(x);      // 把价值放进对应角色
        if (p[id].size() == 1)   // 第一个物品：要交“启动费”
            va[id].push_back(b[id] + c[id]);
        else                     // 后续物品：只交额外费
            va[id].push_back(c[id]);
    }

    /* ---------- 初始化 DP ---------- */
    memset(f, 0x3f, sizeof f);   // 初始设为“无穷大”
    f[0] = 0;                    // 总价值为 0 时代价为 0

    /* ---------- 对每个角色内部按价值降序排序 ---------- */
    for (int i = 0; i < n; i++)
        sort(p[i].begin(), p[i].end(), greater<int>());

    /* ---------- 分组背包 + 费用提前 ---------- */
    for (int i = 0; i < n; i++) {                // 枚举每个角色（组）
        for (int k = v; k >= 0; k--) {           // 逆序刷背包容量
            int value = 0, cost = 0;             // 已选的前 j+1 个物品的总价值/总代价
            for (int j = 0; j < (int)p[i].size(); j++) { // 枚举选多少个该角色物品
                value += p[i][j];
                cost += va[i][j];
                if (k >= value - cost)           // 容量足够“净消耗”
                    f[k] = min(f[k], f[k - value + cost] + cost);
                else                             // 净消耗超过 k，只能直接付 cost
                    f[k] = min(f[k], cost);
            }
        }
    }

    cout << f[v];    // 输出总价值不超过 v 的最小代价
    return 0;
}

无注释

#include<bits/stdc++.h>

using namespace std;

const int N=1010,M=1e6+10;

int n,m,v;
vector<int>p[N],va[N];
int b[N],c[N];
int f[M];

int main(){
    cin>>n>>m>>v;
    for(int i=0;i<n;i++){
        cin>>b[i]>>c[i];
    }
    for(int i=1;i<=m;i++){
        int x,id;
        cin>>x>>id;
        p[id].push_back(x);
        if(p[id].size()==1){
            va[id].push_back(b[id]+c[id]);
        }else{
            va[id].push_back(c[id]);
        }
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=0;i<n;i++)sort(p[i].begin(),p[i].end(),greater());
    for(int i=0;i<n;i++){
        for(int k=v;k>=0;k--){
            int value=0,cost=0;
            for(int j=0;j<p[i].size();j++){
                value+=p[i][j];
                cost+=va[i][j];
                if(k>=value-cost)f[k]=min(f[k],f[k-value+cost]+cost);
                else f[k]=min(f[k],cost);
            }
        }
    }
    cout<<f[v];
}