Jobdu-1455.珍惜生活 感恩现在 多重背包问题

Posted on | In

Question

题目描述

为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾
区，现在假设你一共有资金 n 元，而市场有m种大米，每种大米都是袋装产品， 其价格不等，并且只能整袋购买。请问：你用有限的资金最多能采购多少公斤粮 食呢？

输入
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第 一行是两个整数 n 和 m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的 种类，然后是 m 行数据，每行包含 3 个数 p ， h 和 c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应 种类大米的袋数。

输出
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不 光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

样例输入

1
2
3
4
1
8 2
2 100 4
4 100 2

Answer

在该例中，对每个物品的总数量进行了限制，即多重背包问题。我们对每种 物品进行拆分，使物品数量大大减少，同时通过拆分后的物品间的组合又可以组 合出所有物品数量的情况。

背包拆分

1
2
3
4
5
6
7
8
9
10
int a = 1;
while(c>a){
    c = c-a;
    price[++cnt] = a*p;
    weight[cnt] = a*w;
    a = a*2;
}
price[++cnt] = c*p;
weight[cnt] = c *w;

complete code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.Scanner;
public class main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t--!=0){
            int money = sc.nextInt();
            int kind = sc.nextInt();
            int[] price = new int[2001];
            int[] weight = new int[2001];
            int cnt = 0; //拆分后的物品总数
            while(kind-- != 0){
                int p = sc.nextInt();
                int w = sc.nextInt();
                int c = sc.nextInt();
                
                //背包拆分
                int a = 1;
                while(c>a){
                    c = c-a;
                    price[++cnt] = a*p;
                    weight[cnt] = a*w;
                    a = a*2;
                }
                price[++cnt] = c*p;
                weight[cnt] = c *w; 
            }
            
            //initial
            int[] dp = new int[money+1];
            for(int i=1; i<=money; i++)
                dp[i] = 0;
                
            for(int i=1; i<=cnt; i++){
                for(int j=money; j>=price[i]; j--){
                    dp[j] = Math.max(dp[j], dp[j-price[i]]+weight[i]);
                }
            }
            System.out.println(dp[money]);
        }
        sc.close();
    }
}

Summary

多重背包的特征是每个物品可取的数量为一个确定的整数，我们通过对这个整数进行拆分，使若干个物品组合成一个价值和体积均为这几个物品的和的大物品，同时通过这些大物品的间的组合又可以组合出选择任意件物品所包含的体积和重量情况，通过这种拆分使最后进行 0-1 背包的物品数量大大减少，从而降低复杂度，其时间复杂的为

$$ O(s * \sum_{i=1}^n \log_2(k_i))$$