概述
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
输出
3
解题代码：
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
输出样例：
10
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
输出样例：
10
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)——背包问题的全部内容，希望文章能够帮你解决动态规划(DP)——背包问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复