动态规划(DP)——背包问题-阿里云开发者社区

01背包

01背包问题描述

有一个背包，背包的容量为V，有n个物品，每个物品都有自己所占背包的空间大小和价值，每种物品只能用一次，求如何向背包中放入物品使得价值最大。

解题思路

问题一般可以分为：

1.状态表示 dp[i][j]：

（i为当前考虑是否放入第i个物品，j为当前背包的容量）

状态表示为一个集合，向背包中放入物品的所选方案的集合；

集合中的方案要满足，只从前i个物品中选，且中物品的总体积要小于等于j；

集合中的数据通常为最大值，最小值或者方案数，数量…

2.状态计算：

集合的划分

01背包问题，将集合划分为不包含i和包含i

不包含i——dp[i-1][j]

包含i——dp[i-1][j-vi]+wi

例题

题目来源：

洛谷 P1048 [NOIP2005 普及组] 采药

题目链接

题目描述：

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？

输入格式：

第一行有 22 个整数 TT（1 \le T \le 10001≤T≤1000）和 MM（1 \le M \le 1001≤M≤100），用一个空格隔开，TT 代表总共能够用来采药的时间，MM 代表山洞里的草药的数目。

接下来的 MM 行每行包括两个在 11 到 100100 之间（包括 11 和 100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式：

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例：

输入

70 3

71 100

69 1

1 2

输出

解题代码：

package luogu.dp.背包01;
import java.io.*;
import static java.lang.System.in;
public class P1048 {
    public static void main(String[] args) throws IOException {
        //快读
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        in.nextToken();
        int t = (int) in.nval;//能用来采药的总时间
        in.nextToken();
        int m = (int) in.nval;//草药的数目(种类)
        int[] v = new int[m+1];//每个草药要花费的时间
        int[] w = new int[m+1];//每个草药的价值
        for ( int i=1; i<=m; i++ ) { //读入每个草药所需的时间和价值
            in.nextToken();
            v[i] = (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        int[][] f = new int[m+1][t+1]; //dp 存放所有方案的集合 集合中存放的数据为每种方案的价值
        for( int i=1; i<=m; i++ ) {  //循环尝试是否放入第i个草药
            for ( int j=0; j<=t; j++ ) { //循环背包的容量
                f[i][j] = f[i-1][j]; //前i个物品满足背包容量为j的方案的价值
                //当当前背包的容量大于第i个物品时，尝试放入第i个物品
                //与不放入进行比较，取其中的最大值
                if ( j>=v[i] ) f[i][j] = Math.max( f[i-1][j], f[i-1][j-v[i]]+w[i] );
            }
        }
        out.print(f[m][t]); //输出满足要求的最大价值
        out.flush();
    }
}

空间优化 (采用一维数组) ：

package luogu.dp.背包01;
import java.io.*;
import static java.lang.System.in;
public class P1048 {
    public static void main(String[] args) throws IOException {
        //快读
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        in.nextToken();
        int t = (int) in.nval;//能用来采药的总时间
        in.nextToken();
        int m = (int) in.nval;//草药的数目(种类)
        int[] v = new int[m+1];//每个草药要花费的时间
        int[] w = new int[m+1];//每个草药的价值
        for ( int i=1; i<=m; i++ ) { //读入每个草药所需的时间和价值
            in.nextToken();
            v[i] = (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        // 由于每次多出一个新物品都是在之前的基础上考虑是否放入新物品
        //所以可以采用一维数组从上向下滚动
        int[] f = new int[t+1]; 
        for( int i=1; i<=m; i++ ) {  //循环尝试是否放入第i个草药
            for ( int j=t; j>=v[i]; j-- ) { //循环背包的容量
                //因为从小到大遍历容量数组，前面的数值会影响后面的数值
                //所以反向遍历数组，背包容量小于当前物品所需容量时停止循环
                f[j] = Math.max( f[j], f[j-v[i]]+w[i] );
            }
        }
        out.print(f[t]); //输出满足要求的最大价值
        out.flush();
    }
}

完全背包

完全背包问题描述

有一个背包，背包的容量为V，有n个物品，每个物品都有自己所占背包的空间大小和价值，每种物品可以使用无数次，求如何向背包中放入物品使得价值最大。

解题思路

问题一般可以分为：

1.状态表示 dp[i][j]：

（i为当前考虑是否放入第i个物品，j为当前背包的容量）

状态表示为一个集合，向背包中放入物品的所选方案的集合；

集合中的方案要满足，只从前i个物品中选，且中物品的总体积要小于等于j；

集合中的数据通常为最大值，最小值或者方案数，数量…

2.状态计算：

集合的划分

完全背包问题，将集合划分为k份，每份包含k个第i个物品

1.先去掉k个物品i

2.求MAX，dp[i-1][j-kvi]
3.再加回k个物品i
dp[i-1][j-kvi]+k*w[i]

例题

题目来源：

洛谷 P1616 疯狂的采药

题目链接

题目背景：

此题为纪念 LiYuxiang 而生。

题目描述：

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

11. 每种草药可以无限制地疯狂采摘。

22. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式：

输入第一行有两个整数，分别代表总共能够用来采药的时间 tt 和代表山洞里的草药的数目 mm。

第 22 到第 (m + 1)(m+1) 行，每行两个整数，第 (i + 1)(i+1) 行的整数 a_i, b_ia i ,bi分别表示采摘第 ii 种草药的时间和该草药的价值。

输出格式：

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例：

输入

70 3

71 100

69 1

1 2

输出

140

说明/提示：

数据规模与约定

对于 30%30% 的数据，保证 m \le 10^3m≤10 3。

对于 100%100% 的数据，保证 1 \leq m \le 10^41≤m≤104 ，1 \leq t \leq 10^71≤t≤10 7 ，且 1 \leq m \times t \leq 10^71≤m×t≤10 7 ，1 \leq a_i, b_i \leq 10^41≤a i ,bi ≤104 。

解题代码：

package luogu.dp.完全背包;
import java.io.*;
public class P1616 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        in.nextToken();
        int t = (int) in.nval;//能用来采药的总时间
        in.nextToken();
        int m = (int) in.nval;//草药的数目(种类)
        int[] v = new int[m+1];//每个草药要花费的时间
        int[] w = new int[m+1];//每个草药的价值
        for ( int i=1; i<=m; i++ ) {//读入每个草药所需的时间和价值
            in.nextToken();
            v[i] = (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        long[][] dp = new long[m+1][t+1];//dp 存放所有方案的集合 集合中存放的数据为每种方案的价值
        for ( int i=1; i<=m; i++ ) {//循环尝试是否放入第i个草药
            for ( int j=1; j<=t; j++ ) {//循环背包的容量
                for ( int k=0; k*v[i]<=j; k++ ) {//尝试可以放入草药i的个数
                    //从0开始
                    dp[i][j] = Math.max( dp[i][j], dp[i-1][j-v[i]*k]+w[i]*k );
                }
            }
        }
        out.print(dp[t]);
        out.flush();
    }
}

时间优化：

package luogu.dp.完全背包;
import java.io.*;
public class P1616 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        in.nextToken();
        int t = (int) in.nval;//能用来采药的总时间
        in.nextToken();
        int m = (int) in.nval;//草药的数目(种类)
        int[] v = new int[m+1];//每个草药要花费的时间
        int[] w = new int[m+1];//每个草药的价值
        for ( int i=1; i<=m; i++ ) {//读入每个草药所需的时间和价值
            in.nextToken();
            v[i] = (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        long[][] dp = new long[m+1][t+1];//dp 存放所有方案的集合 集合中存放的数据为每种方案的价值
        for ( int i=1; i<=m; i++ ) {
            for ( int j=0; j<=t; j++ ) {
                //考虑要放入几个草药i时
                //可以在前面的基础上(本行)考虑是否要对放入的草药i的个数加一
                //这样子不用每次进行重新遍历循环
                dp[i][j] = dp[i-1][j];
                //当背包容量大于草药i的所需时间才进行考虑
                if ( j>=v[i] ) dp[i][j] = Math.max( dp[i][j], dp[i][j-v[i]]+w[i] );
            }
        }
        out.print(dp[t]);
        out.flush();
    }
}

空间优化：

package luogu.dp.完全背包;
import java.io.*;
public class P1616 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        in.nextToken();
        int t = (int) in.nval;//能用来采药的总时间
        in.nextToken();
        int m = (int) in.nval;//草药的数目(种类)
        int[] v = new int[m+1];//每个草药要花费的时间
        int[] w = new int[m+1];//每个草药的价值
        for ( int i=1; i<=m; i++ ) {//读入每个草药所需的时间和价值
            in.nextToken();
            v[i] = (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        // 由于每次多出一个新物品都是在之前的基础上考虑是否放入新物品
        //所以可以采用一维数组从上向下滚动
        long[] dp = new long[t+1];
        for ( int i=1; i<=m; i++ ) {
            for ( int j=v[i]; j<=t; j++ ) {
                //因为无限个数，所以不会影响后面的
                //可以采用正序或倒序
                dp[j] = Math.max( dp[j], dp[j-v[i]]+w[i] );
            }
        }
        out.print(dp[t]);
        out.flush();
    }
}

多重背包

与完全背包的差别，物品有指明有多少个可以使用

朴素解法：

例题链接

有 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

输出样例：

package luogu.dp.多重背包;
import java.util.Scanner;
public class acwing多重背包I {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//物品种数
        int m = 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();
        }
        int[][] dp = new int[n+1][m+1];
        //多重背包转化为完全背包
        for ( int i=1; i<=n; i++ ) { //物品的种类
            for ( int j=0; j<=m; j++ ) { //背包容量
                for ( int k=0; k<=s[i]&&k*v[i]<=j; k++ ) { //物品的数量
                    //完全背包，从本行变化而来
                    dp[i][j] = Math.max( dp[i][j], dp[i-1][j-k*v[i]]+k*w[i] );
                }
            }
        }
        System.out.println( dp[n][m] );
    }
}

二进制优化：

题目链接

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

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

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

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000

0<V≤2000

0<vi,wi,si≤2000

提示：

本题考查多重背包的二进制优化方法。

输入样例

4 5

1 2 3

2 4 1

3 4 3

4 5 2

输出样例：

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//物品的种数
        int m = sc.nextInt();//背包容量
        ArrayList<Integer> v = new ArrayList<>();//体积
        ArrayList<Integer> w = new ArrayList<>();//物品的价值
        for ( int i=0; i<n; i++ ) {
            int a = sc.nextInt();//物品的体积
            int b = sc.nextInt();//物品的价值
            int c = sc.nextInt();//物品的数量
            //二进制优化
            int k = 1;
            while ( k<=c ) {
                v.add( a*k );
                w.add( b*k );
                c -= k;
                k *= 2;
            }
            //物品剩余的数量
            if ( c>0 ) {
                v.add( a*c );
                w.add( b*c );
            }
        }
        n = w.size();//更新物品种类的数量
        //接下去与01背包相同
        int[] dp = new int[m+1];
        for ( int i=0; i<n; i++ ) {
            //倒序遍历，防止前面影响后面
            for ( int j=m; j>=v.get(i); j-- ) {
                dp[j] = Math.max( dp[j], dp[j-v.get(i)]+w.get(i) );
            }
        }
        System.out.println( dp[m] );
    }

分组背包

分组背包：

有一个背包，背包的容量为V，有n组物品，每组的每个物品都有自己所占背包的空间大小和价值，每组物品可以选择其中的一个放入背包，求如何向背包中放入物品使得价值最大。

例题：

9. 分组背包问题

题目链接

有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8

package luogu.dp;
import java.io.*;
public class 分组背包 {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws IOException {
        int n = in();
        int v = in();
        int[][] vi = new int[n+1][];
        int[][] wi = new int[n+1][];
        int[] s = new int[n+1];
        for ( int i=1; i<=n; i++ ) {
            s[i] = in();//读入每组的个数
            vi[i] = new int[s[i]+1];
            wi[i] = new int[s[i]+1];
            for ( int j=1; j<=s[i]; j++ ) {
                vi[i][j] = in();
                wi[i][j] = in();
            }
        }
        int[] dp = new int[v+1];
        for ( int i=1; i<=n; i++ ) { //第i组
            for ( int j=v; j>=0; j-- ) { //倒序防止前面影响后面
                for ( int k=1; k<=s[i]; k++ ) {//第i组第j个
                    if ( j>=vi[i][k] ) {
                        dp[j] = Math.max( dp[j], dp[j-vi[i][k]]+wi[i][k] );
                    }
                }
            }
        }
        out.println(dp[v]);
        out.flush();
    }
    public static int in() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}

动态规划(DP)——背包问题

01背包

完全背包

多重背包

分组背包

热门文章

最新文章

相关电子书