背包问题

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author Noperx
 * @Create 2021-07-09 9:24
 */
public class DPTest2 {

    public static void main(String[] args) {
        int[] w = new int[]{1500, 4000, 2000};
        int[] v = new int[]{1, 2, 3};
        int[] m = new int[]{2, 1, 3};
        int V = 8;

//        zeroOrOne(w,v,V);
//        zeroToN(w,v,V);
//        multiple(w, v, V, m);
        multiple3(w, v, V, m);
    }

    /**
     * 0-1背包问题
     * 空间复杂度优化，dp变一维数组
     *
     * @param w 物品价值
     * @param v 物品重量
     * @param V 背包大小
     */
    public static void zeroOrOne(int[] w, int[] v, int V) {
        int[] dp = new int[V + 1];
        for (int i = 1; i <= v.length; i++) {
            for (int j = V; j >= v[i - 1]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
            }
            System.out.println(Arrays.toString(dp));
        }
        System.out.println(dp[V]);
    }

    /**
     * 完全背包问题
     *
     * @param w 物品价值
     * @param v 物品重量
     * @param V 背包大小
     */
    public static void zeroToN(int[] w, int[] v, int V) {
        int[] dp = new int[V + 1];
        for (int i = 1; i <= v.length; i++) {
            for (int j = v[i - 1]; j <= V; j++) {
                dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
            }
            System.out.println(Arrays.toString(dp));
        }
        System.out.println(dp[V]);
    }


    /**
     * 多重背包问题
     *
     * @param w 物品价值
     * @param v 物品重量
     * @param V 背包大小
     * @param m 物品件数
     */
    public static void multiple(int[] w, int[] v, int V, int[] m) {
        int[] dp = new int[V + 1];
        int count = 0;
        for (int i = 1; i <= v.length; i++) {
            for (int j = V; j >= v[i - 1]; j--) {
                for (int k = 1; k <= m[i - 1] && k * v[i - 1] <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * v[i - 1]] + k * w[i - 1]);
                    count++;
                }

            }
            System.out.println(Arrays.toString(dp));
        }
        System.out.println(dp[V]);
        System.out.println(count);
    }


    /**
     * 多重背包问题
     * 二进制优化一步到位方法
     *
     * @param w 物品价值
     * @param v 物品重量
     * @param V 背包大小
     * @param m 物品件数
     */
    public static void multiple2(int[] w, int[] v, int V, int[] m) {
        int[] dp = new int[V + 1];
        int count = 0;
        for (int i = 1; i <= v.length; i++) {
            int k = 1;
            while (k * v[i - 1] < V) {
                for (int j = V; j >= k * v[i - 1]; j--) {
                    if (k <= m[i - 1]) {//二进制式优化
                        dp[j] = Math.max(dp[j], dp[j - k * v[i - 1]] + k * w[i - 1]);
                        count++;
                    } else {//余数
                        dp[j] = Math.max(dp[j], dp[j - m[i - 1]* v[i - 1]] + m[i - 1] * w[i - 1]);
                        count++;
                    }
                }
                m[i - 1] = m[i - 1] - k;
                if(m[i - 1]<=0){//i件物品件数小于等于0时停止循环
                    break;
                }
                k = k<<1;
            }
            System.out.println(Arrays.toString(dp));
        }
        System.out.println(dp[V]);
        System.out.println(count);
    }

    /**
     * 多重背包问题
     * 二进制优化
     * 将m[i]分解为二进制相加形式
     * 例如：12 = 1+2+4+5 = 2^0 + 2^1 +2^2 + 5
     *
     * @param w 物品价值
     * @param v 物品重量
     * @param V 背包大小
     * @param m 物品件数
     */
    public static void multiple3(int[] w, int[] v, int V, int[] m) {
        int[] dp = new int[V + 1];

        ArrayList<Integer> ww = new ArrayList<>();
        ArrayList<Integer> vv = new ArrayList<>();
        for (int i = 0; i < m.length; i++) {//二进制优化，减小加入物品件数
            for (int j = 1; j < m[i]; j<<=1) {
                ww.add(j*w[i]);
                vv.add(j*v[i]);
                m[i] = m[i]-j;
            }
            if (m[i]>0){//余数
                ww.add(m[i]*w[i]);
                vv.add(m[i]*v[i]);
            }
        }
        System.out.println("转换后的w："+ww.toString());
        System.out.println("转换后的v："+vv.toString());

        //转换为0/1问题求解
        for (int i = 0; i < vv.size(); i++) {
            for (int j = V; j >= vv.get(i); j--) {
                dp[j] = Math.max(dp[j], dp[j - vv.get(i)] + ww.get(i));
            }
            System.out.println(Arrays.toString(dp));
        }
        System.out.println(dp[V]);


    }
}

输出

转换后的w：[1500, 1500, 4000, 2000, 4000]
转换后的v：[1, 1, 2, 3, 6]
[0, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500]
[0, 1500, 3000, 3000, 3000, 3000, 3000, 3000, 3000]
[0, 1500, 4000, 5500, 7000, 7000, 7000, 7000, 7000]
[0, 1500, 4000, 5500, 7000, 7000, 7500, 9000, 9000]
[0, 1500, 4000, 5500, 7000, 7000, 7500, 9000, 9000]
9000