完全背包¶

简介¶

题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件，也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……取[V/c]件等很多种。如果仍然按照解01背包时的思路，令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

f[j]=max{f[j],f[j-k*c]+k*w}（0<=k*c<=v）

这跟01背包问题一样有\(O(N*V)\)个状态需要求解，但求解每个状态f[v]的时间是\(O(V/c)\)，总的复杂度是超过\(O(VN)\)的。将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的状态转移方程可以推及其它类型的背包问题。但是由于复杂度太高，我们还是试图改进这个复杂度。

简单有效优化

完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。这个优化可以简单的\(O(N^2)\)地实现，一般都可以承受。另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以\(O(V+N)\)地完成这个优化。这个不太重要的过程就不给出伪代码了，希望你能独立思考写出伪代码或程序。既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c件，于是可以把第i种物品转化为V/c件费用为c[I]及价值w[I]的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。更高效的转化方法是：把第i种物品拆成费用为\(c*2^k\)、价值为\(w*2^k\)的若干件物品，其中k满足\(0<=k<=\log_2(V/c)+1\)。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个\(2^k\)件物品的和。这样把每种物品拆成\(O(log_2(V/c))\)件物品，是一个很大的改进。

最优解法

for i=1..N
    for j=c..V
        f[j]=max{f[j],f[j-c]+w}

你会发现，这个伪代码与01背包的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么**01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[v]是由状态f[v-c]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个没有已经选入第i件物品的子结果f[v-c]。而当前**完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[v-c]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：

f[j]=max{f[j],f[j-c]+w}

将这个方程用一维数组实现，便得到了上面的伪代码。最后抽象出处理一件完全背包类物品的过程伪代码，以后会用到：

procedure CompletePack(c,w)
    for j=c..V
        f[j]=max{f[j],f[j-c]+w}

思想¶

类似01背包，只不过多一层循环，枚举第i件物品取k份(k=1,k++,j-k*w[i]>=0)

注意¶

观察f[i][j]中保存的信息，我们可以把k循环去掉，请思考！

例题 #1¶

设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M ，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M ，而价值的和为最大。

解决¶

#include <bits/stdc++.h>
using namespace std;
int m, n, w[205], c[205], f[205][205];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> c[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j < w[i])
                f[i][j] = f[i - 1][j];

            else if (f[i - 1][j] > f[i][j - w[i]] + c[i])
                f[i][j] = f[i - 1][j];
            else
                f[i][j] = f[i][j - w[i]] + c[i];
        }
    }

    cout << "max=" << f[n][m];
    return 0;
}

例题 #2 software¶

题目描述

一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成 \(m\) 个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件。

输入格式

输入文件第一行包含两个由空格隔开的整数 \(n\) 和 \(m\)，其中 \(1 \le n \le 100\)，\(1 \le m \le 100\)，接下来的 \(n\) 行每行包含两个用空格隔开的整数 \(d_1\) 和 \(d_2\)，\(d_1\) 表示该技术人员完成第一个软件中的一个模块所需的天数，\(d_2\) 表示该技术人员完成第二个软件中的一个模块所需的天数，其中 \(1 \le d_1,d_2 \le 100\)。

输出格式

输出文件仅有一行包含一个整数 \(d\)，表示公司最早能于 \(d\) 天后交付软件。

先考虑二分答案。然后我们就要判断在t时间下能否做出m件A和m件B。

发现m很小，所以我们可以枚举一个，求另一个的最大值。于是就是f_{i,j}表示前i个人完成j个A后最多完成多少B。完全背包即可。

// Problem: P1800 software
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1800
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read()
{
  int xx = 0, ff = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9')
  {
    if (ch == '-')
      ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
    cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
    for (auto v: a) cerr << v << ' ';
    err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
    cerr << a << ' ';
    err(x...);
}
#else
#define dbg(...)
#endif
const int N=100+5;
const ull P=137;
const int INF=1e18+7;
/*

策略


*/  
int f[N][N];//前i个人完成j个A后最多完成多少B
int n,m;
int a[N],b[N];


bool check(int t){

    memset(f,-0x3f3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=m;~j;j--){
            for(int k=0;k<=j&&a[i]*k<=t;k++){
                f[i][j]=max(f[i][j],f[i-1][j-k]+(t-a[i]*k)/b[i]);
            }
        }
    }

    return f[n][m]>=m;
}

signed main(){
     n=rd,m=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd;
        b[i]=rd;
    }

    int l=0,r=10000000;
    int res=0;
    while(l<=r){
        int mid=l+r>>1;

        if(check(mid))r=mid-1,res=mid;
        else l=mid+1;
    }

    // cdbg(check(16));

    cout<<res<<endl;

}