$$\color{Red}{分组背包问题:机器分配:(1暴力搜索，2分组背包)}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

暴力思路

dfs(int num, int sum, int res)
num代表当前枚举的是第几个公司，sum代表枚举的前num - 1个选择方案，目前所获得的价值总和，res代表还剩可选的机器数量

每当枚举到最后一个公司的时候，我们即可把剩下所有的机器数量都划分给它，然后获取它的w[i][res]加入sum中，如果此时的价值超过此前最大的情况，刷新答案ans_cnt数组为当前所搜索树的选择方案

java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n, m, ans, N = 11, M = 16;
    static int[][] w = new int[N][M];
    static int[] cnt = new int[M];
    static int[] ans_cnt = new int[M];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void dfs(int num, int sum, int res){
        if(num == n){
            sum += w[n][res];
            cnt[n] = res;
            if(sum > ans){
                ans = sum;
                System.arraycopy(cnt, 1, ans_cnt, 1, n);
            }
            return;
        }
        for (int i = 0; i <= res; i++) {
            cnt[num] = i;
            dfs(num + 1, sum + w[num][i], res - i);
        }
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            String[] s2 = br.readLine().split(" ");
            for (int j = 1; j <= m; j++)
                w[i][j] = Integer.parseInt(s2[j-1]);
        }

        dfs(1, 0, m);
        System.out.println(ans);
        for (int i = 1; i <= n; i++)
            System.out.println(i + " " + ans_cnt[i]);
    }
}

分组背包思路

我们根据题干很容易联想到每个公司相当于一个组，而选择分配给该公司k个物品，这个物品的k，即代表着体积v，而对应的价值就是w[i][k]
那么我们就把这道题化作了一个分组背包问题，从n个组中，每组有m个物品，且体积等于它位于组内的序号数

而求方案数和我们之前做的01背包求方案数差不多，我们动态规划的方向要和我们找寻方案的方向相反，并且判断是否可选的主要条件就是动态规划的条件
f[i][j] == f[i - 1][j - k] + w[i][k]
而我们找到了符合的k值，即第n组选k个，那么倒序遍历的j就需要赋值j = j - k 并且因为已经找寻到了最佳k值，就不需要循环到最大的j，可以直接break出去，进行i-1组的最佳选取查询

java分组背包做法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n, m, N = 11, M = 16;
    static int[][] w = new int[N][M];
    static int[][] f = new int[N][M];
    static int[] way = new int[M];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            String[] s2 = br.readLine().split(" ");
            for (int j = 1; j <= m; j++)
                w[i][j] = Integer.parseInt(s2[j - 1]);
        }

        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= j; k++)
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k] + w[i][k]);

        System.out.println(f[n][m]);

        for (int i = n, j = m; i >= 1; i--)
            for (int k = 0; k <= j; k++)
                if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
                    way[i] = k;
                    j -= k;
                    break;
                }
        for (int i = 1; i <= n; i++) System.out.println(i + " " + way[i]);
    }
}