如题：如何写一个完全背包算法。需要打印出取的那些物品，分别取了几次

Question

有编号分别为a,b,c,d,e的N=5件物品，它们的重量w分别是2,2,6,5,4，它们的价值v分别是6,3,5,4,6，他们的体积是c分别是3,5,2,6,4，现在给你个承重为M=10，体积是15的背包。算出最优的组合，物品可以重复放入背包

Answer 1

public class test {
    static int V = 15;
    static int W = 10;
    static int N = 5;
    static int[] values = { 6, 3, 5, 4, 6 };
    // static int[] volume = { 3, 5, 2, 4, 6 };
    static int[] volume = { 10, 5, 2, 6, 4 };

    static int[] weights = { 2, 2, 6, 5, 4 };
    static int[][][] pack = new int[W + 1][V + 1][N];// 定义包裹,pack[1][2][3]表示重量为1，容量为2的包裹里放了多少个物品4（物品以0索引）
    static int[][] value = new int[W + 1][V + 1];// 定义包裹价值,value[1][2]表示重量为1，容量为2的包裹的最大价值

    public static void main(String[] args) {
        for (int i = 0; i < W + 1; i++) {// 遍历重量
            for (int j = 0; j < V + 1; j++) {// 遍历容量
                if (i == 0 || j == 0) {// 如果重量或者容量为0
                    value[i][j] = 0;// 包裹的最大价值为0
                } else {// 否则
                    value[i][j] = value[i][j - 1];// 初始化包裹价值等于同重量容量小一的包裹
                    pack[i][j] = pack[i][j - 1];
                    for (int k = 0; k < N; k++) {// 遍历物品
                        if ((i >= weights[k]) && (j >= volume[k])) {// 如果包裹装的下该物品
                            if (value[i - weights[k]][j - volume[k]] + values[k] > value[i][j]) {// 如果装下该物品后，剩下的空间取最优选择，所得的总和价值如果大于之前的包裹价值
                                pack[i][j] = pack[i - weights[k]][j - volume[k]].clone();// 包裹装填该物品
                                pack[i][j][k]++;// 包裹装填该物品
                                value[i][j] = value[i - weights[k]][j - volume[k]] + values[k];// 更新包裹价格
                            }
                        }
                    }
                }
            }
        }
        String str = "最大价值是" + value[W][V];// 打印最大价值
        System.out.println(str);
        for (int i = 0; i < N; i++) {// 打印包裹物品情况
            str = "第" + (i + 1) + "个物品的数量是" + pack[W][V][i];
            System.out.println(str);
        }
    }
}

允许重复挑选，数值有很大的时候可以用贪心法，以减小空间复杂度。

public class test {

    static int V = 32291; // 背包所承载的最大容量
    static int W = 64582; // 背包所承载的最大重量
    static int N = 3; // 物品数目
    static double[] values = { 24078.6, 17640, 5716.48 }; // 每个物品的价值
    static int[] volume = { 2450, 2450, 1540 }; // 每个物品的体积
    static int[] weights = { 13230, 8820, 2464 }; // 每个物品的重量
    static int[] pack = new int[N];// 定义包裹
    static double value = 0;// 定义包裹价值
    static int Vtmp = V;
    static int Wtmp = W;

    public static void main(String[] args) {
        while (true) {
            double maxV = 0;
            int k = 0;
            for (int i = 0; i < N; i++) {
                int num;
                if (Vtmp / volume[i] > Wtmp / weights[i]) {
                    num = Wtmp / weights[i];
                } else {
                    num = Vtmp / volume[i];
                }
                if (maxV < num * values[i]) {
                    maxV = num * values[i];
                    k = i;
                }
            }
            if (maxV == 0) {
                break;
            }
            Vtmp -= volume[k];
            Wtmp -= weights[k];
            value += values[k];
            pack[k]++;
        }

        String str = "最大价值是" + value;// 打印最大价值
        System.out.println(str);
        for (int i = 0; i < N; i++) {// 打印包裹物品情况
            str = "第" + (i + 1) + "个物品的数量是" + pack[i];
            System.out.println(str);
        }
    }
}