完全背包-蒲公英云

完全背包

完全背包和01背包的区别

01背包：有n个物品，每种物品只能被使用一次

完全背包：有n个物品，每个物品可以被多次使用

完全背包的递推公式可以由01背包的递推公式扩展得到(如果背包可以装下k个weight[i])
二维：
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-k*weight[i]] + k*value[i])
一维
dp[j] = Math.max(dp[j],dp[j-k*weight[i]]+k*value[i])
当可以放入第i件物品的时候，要尽可能多的装入第i件物品
二维代码：

import java.util.Scanner;
public class Wanquanbeibao {
    static int[][] dp;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] value = new int[n+1];
        int[] weight = new int[n+1];
        for (int i = 1; i <= n; i++) {
            value[i] = in.nextInt();
            weight[i] = in.nextInt();
        }
        dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k*weight[i] <= j; k++) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-k*weight[i]]+k*value[i]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

一维代码：

import java.util.Scanner;
public class Wanquanbeibao1 {
    static int[] dp;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] value = new int[n+1];
        int[] weight = new int[n+1];
        for (int i = 1; i <= n; i++) {
            value[i] = in.nextInt();
            weight[i] = in.nextInt();
        }
        dp = new int[m+1];
        for (int i = 1; i <= n; i++) {
            //与01背包不同的是j的循环是从1到m
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k*weight[i] <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j-k*weight[i]]+k*value[i]);
                }
            }
        }
        System.out.println(dp[m]);
    }
}

之前看到一个大牛写的很简洁的完全背包的一维代码，移步大牛代码
大牛的代码思路是不论同一个物品装入多少次，都是一次装入一个，所以问题转换成在装入第i个物品之后继续装第i种物品，以下将大神的c代码转为java代码

import java.util.Scanner;
public class Wanquanbeibao2 {
    static int[] dp;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] value = new int[n+1];
        int[] weight = new int[n+1];
        for (int i = 1; i <= n; i++) {
            value[i] = in.nextInt();
            weight[i] = in.nextInt();
        }
        dp = new int[m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
   //与01背包唯一的不同点
                if(j >= weight[i])
                    dp[j] = Math.max(dp[j], dp[j-weight[i]]+value[i]);
            }
        }
        System.out.println(dp[m]);
    }
}