多重背包问题1

题目来源于acwing

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，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

这次背包问题与0-1背包不同在于，每种物品既不是0或1次，也不是无限次，他们有确定的个数。
最简单的想法只需要在0-1背包的代码上更改，用三次for循环，最内侧表示这个物品用了k次，因为数据量不大，所以也ok。

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

import java.util.*;

public class Main {
    public static int solve(int N,int V,int[] v,int[] w,int[] s) {
    //主体代码
        int[] dp = new int[V + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = V; j >= v[i]; j--) {
                for (int k = 1; k <= s[i]; k++) {
                    if (j >= k * v[i])
                    dp[j] = Math.max(dp[j],dp[j - k *v[i]] + k * w[i]);
                    //第i个物品放k次
                }
                
            }
            //show(dp);
        }
        return dp[dp.length - 1];
        
    }
    public static void show(int[] arr) {
        for (int i = 0; i <arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println("*");
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[] s = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }
        System.out.println(solve(N,V,v,w,s));
    }
}

如果数据范围变大了怎么办

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

方法 :对最内层的循环优化。可以把s个当前物品全部拆开，每个数组位置只装一个物品，变成一堆0-1背包的问题，但是这样时间复杂度没变，有一种更高效的拆法。
对于任意数，可以分成n个数，用这n个数中某些的和表示比他小的数。
比如7，可以分解为1,2，4.每个数只能用一遍
那么

• 1=1
• 2=2
• 3=1+2
• 4=4
• 5=1+4
• 6=2+4
• 7=1+2+4
  那么10怎么分呢
  分为1,2，4,3。取1,2，4,8也可以。
  这样最内层复杂度就是log(N)。最后又转化成了0-1背包问题。
  原题在这↓↓
  多重背包问题2
  更改的地方会有标记

  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 44 45 46 47 48 49

  import java.util.*; public class Main { public static int solve(int N,int V,int[] v,int[] w,int[] s,ArrayList<Integer> listv,ArrayList<Integer> listw) { int[] dp = new int[V + 1]; //这里传参更改了，其实原来的v和w数组已经没用了 for (int i = 0; i < listv.size(); i++) {//拆成了更多的部分 for (int j = V; j >= listv.get(i); j--) { dp[j] = Math.max(dp[j],dp[j - listv.get(i)] + listw.get(i)); } //show(dp); } return dp[dp.length - 1]; } public static void show(int[] arr) { for (int i = 0; i <arr.length; i++) { System.out.print(arr[i]+" "); } System.out.println("*"); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[] v = new int[N + 1]; int[] w = new int[N + 1]; int[] s = new int[N + 1]; ArrayList<Integer> listv = new ArrayList<>(1001); ArrayList<Integer> listw = new ArrayList<>(1001); for (int i = 1; i <= N; i++) { v[i] = sc.nextInt(); w[i] = sc.nextInt(); s[i] = sc.nextInt(); //下面是新增的地方，为了算出来当前应该分成几份，以及每一份都是什么 for (int j = 1; j <= s[i]; j *= 2) { s[i] -= j; //这里是参照别人写的，这个写法是真的厉害，因为一般情况下循环的跳出条件是不会变的，这里更改了跳出条件 listv.add(v[i] * j); listw.add(w[i] * j); } if (s[i] > 0) { //对于10的情况，最后会剩下一个3 listv.add(v[i] * s[i]); listw.add(w[i] * s[i]); } } System.out.println(solve(N,V,v,w,s,listv,listw)); } }