问题定义

有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

事实上是在01背包的问题上增加条件:第i个物品可以选s[i]个.

状态分析

朴素思路

• 前i个物品不超过j的最大价值=max(当前价值,取k个i物品(k从0到s[i])的价值+体积-k*v[i]条件下取前i-1个物品的价值)
• 注意实际实现的过程中k不一定能取到s[i],因为体积可能会不够.
• 因为只用到i-1的状态,故可以通过滚动数组优化.//由于下方二进制优化使用一维数组这里朴素做法就不写了
• 本质上问题抽象成状态空间,通过状态转移来计算
• 不能像完全背包一样优化

详细注释代码I

/*
 * @Author: ACCXavier
 * @Date: 2021-04-27 10:51:10
 * @LastEditTime: 2021-04-27 15:59:04
 * Bilibili:https://space.bilibili.com/7469540
 * 题目地址:https://www.acwing.com/problem/content/4/
 * @keywords: 多重背包问题 I
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
 */
#include <iostream>
using namespace std;
const int N = 110;
int v[N], w[N], s[N];
int f[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)//从1开始
        cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; ++i) {//i遍历物品
        for (int j = 0; j <= m; ++j) {//j遍历体积
            for (int k = 0; k * v[i] <= j && k <= s[i]; k++) {//k遍历第i个物品拿的数量 有两个判断条件,拿的体积要小于当前体积和拿的数量不能超过s[i]
           //     if (k == 0) f[i][j] = max(f[i - 1][j], f[i - 1][j - k * v[i]] + k * w[i]);
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
//如果按照01背包的写法那么f[i][j]应该从f[i-1][j]和f[i-1][j-k*v[i]]+k*w[i]转移过来,但是这里max第一项写的是f[i][j].
//f[i][j] = max(f[i-1][j], f[i - 1][j - k * v[i]] + k * w[i]);//惯常思路
//写f[i-1][j]错误的原因是,取不同k下标的值只要大于f[i-1][j]就会被更新,而事实上要找的是取不同k下标的最大值,所以max第一项要写成f[i][j]
//举个例子,有一个守擂台a和一个挑战者集合B,如果B中有人打败a就应该替换a,让别人挑战自己;而不是挑战者只能和a打,打败a就能守擂.
//那么你会问f[i][j]一开始不是0吗,不取f[i-1][j],不会漏掉情况吗?事实上不会,当k=0时,f[i][j] = max(f[i][j],f[i-1][j]),这一步就会把f[i-1][j]的值转移过来
            }
        }
    }
    cout << f[n][m];

    return 0;
}

二进制优化

• 原理:把一个一个遍历单种物品可以拿的数量转化为一堆一堆的拿,来把遍历数量的复杂度从O(s)降到O(logs)
• 实现思路和证明:
  • 把s分为2的倍数的堆(其实就是把s看成二进制)堆的大小为1,2,4,8,…2^k(k代表这些数字求和值小于等于s时能取到最大的k),其实也就是从二进制s最低位到最高位的前一位的所有位代表的数值,然后把s剩下的分一堆为c,那么,(如果不小于那么k可以取到k+1)
  • 由于1~2^k可以凑出[1,2^(k+1)-1],加上c可以凑出[c,2^(k+1)-1+c]=[c,s]个数,而c<2^(k+1)等价于c<=2^(k+1)-1,所以两个区间之间没有缝隙,正好能够凑出1~s,而0只需要不选即可,故分堆可以凑出所有的数
  • 那么现在只需要遍历logs个物品堆就可以,等价于把多重背包拆成了物品变多的01背包
  • 时间复杂度O(m*nlogs) nlogs是拆分后的物品数量,m是体积

详细注释代码II

/*
 * @Author: ACCXavier
 * @Date: 2021-04-27 16:16:10
 * @LastEditTime: 2021-04-27 16:52:48
 * Bilibili:https://space.bilibili.com/7469540
 * 题目地址:https://www.acwing.com/problem/content/5/
 * @keywords: 多重背包II
有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
 */

#include <iostream>
using namespace std;
const int N = 25000,M = 2010;//题给n2000,s2000,logs<12,开到25000保险
int f[M],w[N],v[N];//

int main()
{
    int n,m;cin>>n>>m;
    int cnt = 0;//拆包数量/分堆数量
    for(int i = 0; i < n; ++ i){
        int vi,wi,s;
        int k = 1;//堆大小
        cin>>vi>>wi>>s;
        //分堆过程
        while(k<=s){//小于等于和小于都可以,因为如果出现等于的情况就是s=2^(k+1)-1,下面的if判断会处理掉
            cnt++;//cnt先++=>下标从1开始
            w[cnt] = k * wi;//k个物品为一堆
            v[cnt] = k * vi;
            s-=k;
            k*=2;
        }
        if(s>0){//如果存在最后一个堆
            cnt ++;
            //最后一个堆有s'个i物品
            w[cnt] = s * wi;
            v[cnt] = s * vi;
        }

    }
    n = cnt;//物品由n个变成了nlogs个 别忘了这句
    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]<<endl;


    return 0;
}