@[toc]
D5 背包型动态规划
Backpack I
Problem:
给定N个物品,重量分别为正整数A0,A1,...,AN-1
,一个 背包最大承重是正整数M,最多能带走多重的物品
样例 :
1 2 输入: 4个物品,重量为2,3,5,7。背包最大承重是11 输出: 10(三个物品:2,3,5)
确定状态:
如果前N-1个物品能拼出W,当然前N个物品也能拼出W
如果前N-1个物品能拼出W-A(N-1),再加上最后的物品A(N-1),拼出W
转移方程: 设f[i][w]=f[i-1][w] OR f[i-1][w-A(i-1)]
能否用前i个物品拼出重量w
能否用前i-1个物品拼出重量w
能否用前i-1个物品拼出重量w-A(i-1),再加上第i个物品
初始条件:
f[0][0] = TRUE:
0个物品可以拼出重量0
f[0][1...M] = FALSE:
0个物品不能拼出大于0的重量
边界情况: f[i-1][w-A(i-1)] 只能在w>=A(i-1)时使用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 public int backPack (int m, int [] A) { int n = A.length; if (n == 0 ) return 0 ; boolean [][] f = new boolean [n + 1 ][m + 1 ]; int [][] pi = new int [n+1 ][m+1 ]; int i, j; f[0 ][0 ] = true ; for (i = 1 ; i <= m; i++) { f[0 ][i] = false ; } for (i = 1 ; i <= n; i++) { for (j = 0 ; j <= m; j++) { f[i][j] = f[i - 1 ][j]; pi[i][j]=0 ; if (j >= A[i - 1 ]) { if (f[i-1 ][j-A[i-1 ]]){ pi[i][j]=1 ; } f[i][j] = f[i][j] | f[i - 1 ][j - A[i - 1 ]]; } } } int res = 0 ; for (i = m; i >= 0 ; i--) { if (f[n][i] == true ) { res = i; break ; } } System.out.println("Put the following items in the backpack:" ); i=res; for (j=n;j>=1 ;j--){ if (pi[i][j]==1 ){ System.out.println(A[j-1 ]); i -= A[j-1 ]; } } return res; }
Backpack V
Problem:
Given n items with size nums[i] which an integer array and all positive numbers. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.
Each item may only be used once.
Example
1 2 3 4 5 6 Given candidate items [1,2,3,3,7] and target 7, A solution set is: [7] [1, 3, 3] return 2
分析
和前一题Backpack不一样的是,我们需要求出有多少组合的和是Target,而不是能不能拼出Target
转移方程: f[i][w]=f[i-1][w] + f[i-1][w-A(i-1)]
用前i个物品有多少种方式拼出重量w
用前i-1个物品有多少种方式拼出重量w
用前i-1个物品有多少种方式拼出重量w-A(i-1),再加上第i个物品
初始条件:
f[0][0]=1:
0个物品可以有一种方式拼出重量0
f[0][1...M]=0:
0个物品不能拼出大于0的重量
边界情况: f[i-1][w-A(i-1)]
只能在w>=A(i-1)时使用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public int backPack (int [] A,int m) { int n = A.length; if (n == 0 ) return 0 ; int [] f = new int [m+1 ]; int i,j; f[0 ] = 1 ; for (i = 1 ; i <= m; i++) { f[i] = 0 ; } for (i = 1 ; i <= n; i++) { for (j = m; j >= 0 ; j--) { if (j >= A[i - 1 ]) { f[j] += f[j - A[i - 1 ]]; } } } return f[m]; }
Backpack VI
Problem
给定N个正整数:A0,A1,…,A(N-1),一个正整数Target,求有多少种组合加起来是Target,每个Ai可以用多次
Example
1 2 input: A=[1,2,4],Target=4 output: 6(1+1+1+1=4,2+2=4,1+1+2=4,1+2+1=4,2+1+1=4,4=4)
分析
任何一个正确的组合中,所有物品总重量是Target
如果最后一个物品重量是K,则前面的物品重量是Targert-K
转移方程:
设f[i] = 有多少种组合能拼出重量 i f[i]=f[i-A0]+f[i-A1]+...+f[i-A(N-1)]
多少种组合能拼出i
多少种组合能拼出i-A0
多少种组合能拼出i-A(N-1)
初始条件:f[0]
= 1 有一种组合能拼出重量0(什么都不选)
1 2 3 4 5 6 7 8 9 10 11 12 13 public int backPackVI (int [] A,int m) { int [] f = new int [m+1 ]; int i,j; f[0 ] = 1 ; for (i = 1 ; i <= m; i++) { for (j = 0 ; j < A.length; j++) { if (i >= A[j]) { f[i] += f[i - A[j]]; } } } return f[m]; }
Backpack II(01背包)
Problem
Given n items with size A[i] and value V[i], and a backpack with size m. What’s the maximum value can you put into the backpack?
Note
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.
Example
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.
转移方程
设f[i][w]
=前i个物品拼出重量w时最大总价值(-1表示不能拼出w)
f[i][w] = max{f[i-1][w],f[i-1][w-A(i-1)]+V(i-1)|w>=A(i-1)且f[i-1][w-A(i-1)]!=-1}
用前i个物品拼出重量w时最大总价值
用前i-1个物品拼出重量w时最大总价值
用钱i-1个物品拼出重量w-A(i-1)时最大总价值,加上第i个物品
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); int n = sc.nextInt(); int [] val = new int [n+1 ]; int [] w = new int [n+1 ]; int [] dp = new int [t+1 ]; for (int i=1 ;i<=n;i++){ w[i] = sc.nextInt(); val[i] = sc.nextInt(); for (int j=t;j>=w[i];j--){ dp[j] = Math.max(dp[j],dp[j-w[i]]+val[i]); } } System.out.println(dp[t]); } } public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); int n = sc.nextInt(); int val,w; int [] dp = new int [t+1 ]; for (int i=1 ;i<=n;i++){ w = sc.nextInt(); val = sc.nextInt(); for (int j=t;j>=w;j--){ dp[j] = Math.max(dp[j],dp[j-w]+val); } } System.out.println(dp[t]); } } public int backPackII (int m,int [] A,int V[]) { int n = A.length; if (n==0 )return 0 ; int [][] f = new int [n+1 ][m+1 ]; int i,w; f[0 ][0 ]=0 ; for (i=1 ;i<=m;i++){ f[0 ][i] = -1 ; } for (i=1 ;i<=n;i++){ for (w=0 ;w<=m;w++){ f[i][w] = f[i-1 ][w]; if (w>=A[i-1 ]&&f[i-1 ][w-A[i-1 ]]!=-1 ){ f[i][w] = Math.max(f[i][w],f[i-1 ][w-A[i-1 ]]+V[i-1 ]); } } } int res=0 ; for (w=0 ;w<=m;w++){ if (f[n][w]!=-1 ){ res = Math.max(res,f[n][w]); } } return res; }
Backpack III(完全背包)
转移方程
设f[i][w]
=前i种 物品拼出重量w时最大总价值(-1表示不能拼出w)
f[i][w] = max(k>=0){f[i-1][w-k*A(i-1)]+k*V(i-1)}
用前i种 物品拼出重量w时最大总价值
用前i-1种 拼出重量w-k*A(i-1)时最大总价值,加上k个第i种物品
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 public class Main { public static void main (String [] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int [] dp = new int [m + 1 ]; int [] val = new int [n + 1 ]; int [] w = new int [n + 1 ]; for (int i = 1 ; i <= n; i++) { w[i] = sc.nextInt(); val[i] = sc.nextInt(); for (int j = w[i]; j <=m; j++) { dp[j] = Math.max (dp[j],dp[j - w[i]]+val[i]); } } System.out.println (dp[m]); } } #include <bits/stdc++.h> using namespace std ;int V[1001 ],W[1001 ],n;void backPackII (int b,int W[],int V[]) { if (n==0 ) return ; int f[n+1 ][b+1 ],I[n+1 ][b+1 ]; for (int i=0 ;i<=b;i++){ f[0 ][i] = 0 ; I[0 ][i] = 0 ; } for (int i=0 ;i<=n;i++){ f[i][0 ] = 0 ; I[i][0 ] = 0 ; } for (int i=1 ;i<=n;i++){ for (int j=0 ;j<=b;j++){ f[i][j]=f[i-1 ][j]; I[i][j]=I[i-1 ][j]; if (j>=W[i-1 ]&&f[i][j]<=f[i][j-W[i-1 ]]+V[i-1 ]){ f[i][j] = f[i][j-W[i-1 ]]+V[i-1 ]; I[i][j] = i; } } } cout <<endl ; cout <<"优化函数:" <<endl ; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <=b; j++) { cout <<f[i][j]<<" " ; } cout <<endl ; } cout <<endl ; cout <<"标记函数:" <<endl ; for (int i = 1 ; i <=n; i++) { for (int j = 1 ; j <=b; j++) { cout <<I[i][j]<<" " ; } cout <<endl ; } int x[n+1 ]; for (int j=1 ;j<=n;j++){ x[j]=0 ; } int y = b,j=n; do { j = I[j][y]; x[j]=1 ; y = y-W[j-1 ]; while (I[j][y]==j){ y = y-W[j-1 ]; x[j] = x[j]+1 ; } }while (I[j][y]!=0 ); cout <<endl ; cout <<"背包回溯:" <<endl ; for (int j2 = 1 ; j2 <=n; j2++) { cout <<"第" <<j2<<"个物品装" <<x[j2]<<"个" <<endl ; } cout <<endl ; cout <<"当前背包所能装载的最大价值为:" <<f[n][b]<<endl ; } int backPack (int b,int W[],int V[]) { if (n==0 )return 0 ; int f[b+1 ]; int i,w; f[0 ]=0 ; for (i=1 ;i<=b;i++){ f[i] = -1 ; } for (i=1 ;i<=n;i++){ for (w=0 ;w<=b;w++){ if (w>=W[i-1 ]&&f[w-W[i-1 ]]!=-1 ){ f[w] = max (f[w],f[w-W[i-1 ]]+V[i-1 ]); } } } int res=0 ; for (w=0 ;w<=b;w++){ if (f[w]!=-1 ){ res = max (res,f[w]); } } return res; } int main () { int b; cout <<"请输入物品个数" <<endl ; cin >>n; cout <<"请输入分别输入物品的价值" <<endl ; for (int i=0 ;i<n;i++) cin >>V[i]; cout <<"请输入分别输入物品的重量" <<endl ; for (int i=0 ;i<n;i++) cin >>W[i]; cout <<"请输入您的背包容量" <<endl ; cin >>b; cout <<"空间复杂度为O(n*m)的方法:" <<endl ; backPackII(b,W,V); cout <<endl ; cout <<"空间复杂度为O(n)的方法:" <<endl ; cout <<"所求出背包所能装载的最大价值" <<backPack(b,W,V)<<endl ; return 0 ; }
Backpack小结
Backpack 可行性 背包
要求不超过Target时能拼出的最大重量
记录前i个物品能不能拼出重量w
Backpack V,Backpack VI,计数型 背包
要求有多少种方式拼出重量Target
Backpack V:记录前i个物品有多少种方式拼出重量w
Backpack VI:记录有多少种方式拼出重量w
BackpackII,BackpackIII,最值型 背包
要求能拼出最大价值
记录f[i][w]
= 前 i 个/种 物品能拼出重量w能得到的最大价值
关键点
最后一步:
最后一个背包内的物品是哪个
最后一个物品有没有进背包
数组大小和最大承重Target有关
小A买菜
Problem
不过uim
由于买了一些辅(e)辅(ro)书
,口袋里只剩M元(M≤10000)。
餐馆虽低端,但是菜品种类不少,有N种(N≤100),第i种卖ai元(ai≤1000)。由于是很低端的餐馆,所以每种菜只有一份。
小A
奉行“不把钱吃光不罢休”,所以他点单一定刚好吧uim
身上所有钱花完。他想知道有多少种点菜方法。
由于小A
肚子太饿,所以最多只能等待11秒。
输入格式
第一行是两个数字,表示N和M。
第二行起N个正数ai(可以有相同的数字,每个数字均在1000以内)。
输出格式
一个正整数,表示点菜方案数,保证答案的范围在int之内。
输入 #1
输出 #1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 const int maxn=10000 +10 ;int v[maxn],f[maxn];int main () { int n,m; cin >>n>>m; f[0 ]=1 ; for (int i=1 ;i<=n;++i) cin >>v[i]; for (int i=1 ;i<=n;++i) for (int j=m;j>=v[i];--j) f[j]+=f[j-v[i]]; cout <<f[m]<<endl ;最后把最后一个点的花费输出来就可以了 return 0 ; }
最大约数和
Problem
选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。
输入格式
输入一个正整数S。S<=1000
输出格式
输出最大的约数之和。
样例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int [] dp = new int [n+1 ]; for (int i=1 ;i<=n;i++){ int v=0 ; for (int j=1 ;j<i;j++){ if (i%j==0 ){ v+=j; } } for (int j=n;j>=i;j--){ dp[j] = Math.max(dp[j],dp[j-i]+v); } } System.out.println(dp[n]); } }
精卫填海
Problem
东海未填平的区域还需要至少体积为v的木石才可以填平,而西山上的木石还剩下n块,每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了,她也很累了,她还剩下的体力为c。
输入格式
输入文件的第一行是三个整数:v、n、c。
从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。
对于100%的数据,0<n<=10000,所有读入的数均属于[0,10000],最后结果<=c。
输出格式
输出文件只有一行,如果精卫能把东海填平,则输出她把东海填平后剩下的最大的体力,否则输出’Impossible’(不带引号)
样例
1 2 3 4 5 6 7 8 9 10 11 12 13 Input 1 100 2 10 50 5 50 5 Output 1 0 Input 2 10 2 1 50 5 10 2 Output 2 Impossible
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int v = sc.nextInt(); int n = sc.nextInt(); int m = sc.nextInt(); int [] dp = new int [m + 1 ]; int w,val; for (int i = 1 ; i <= n; i++) { val = sc.nextInt(); w = sc.nextInt(); for (int j = m; j >= w; j--) dp[j] = Math.max(dp[j], dp[j - w] + val); } for (int i = 1 ; i <=m; i++) { if (dp[i] >= v) { System.out.println(m - i); return ; } } System.out.println("Impossible" ); return ; } }
集合 Subset Sums
题目描述
对于从 1∼n 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的。举个例子,如果 n=3,对于 {1,2,3} 能划分成两个子集合,每个子集合的所有数字和是相等的:
{3}和 {1,2} 是唯一一种分法(交换集合位置被认为是同一种划分方案,因此不会增加划分方案总数) 如果 n=7,有四种方法能划分集合 {1,2,3,4,5,6,7},每一种分法的子集合各数字和是相等的:
{1,6,7} 和 {2,3,4,5} {2,5,7} 和 {1,3,4,6} {3,4,7} 和 {1,2,5,6} {1,2,4,7} 和 {3,5,6}
给出 n,你的程序应该输出划分方案总数。
输入格式
输入文件只有一行,且只有一个整数 n.对于 100% 的数据,1≤n≤39。
输出格式
输出划分方案总数。
样例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = (1 + n) * n / 2 ; if ((m & 1 ) == 1 ) { System.out.println(0 ); return ; } long [] dp = new long [m + 1 ]; dp[0 ] = 1 ; for (int i = 1 ; i <= n; i++) { for (int j = m / 2 ; j >= i; j--) { dp[j] += dp[j - i]; } } System.out.println(dp[m / 2 ] / 2 ); } }
通天之分组背包
Problem
自 01 背包问世之后,小 A 对此深感兴趣。一天,小 A 去远游,却发现他的背包不同于 01 背包,他的物品大致可分为 k 组,每组中的物品相互冲突,现在,他想知道最大的利用价值是多少。
输入格式
两个数 m,n,表示一共有 n 件物品,总重量为 m。1≤m,n≤1000。
接下来 n 行,每行 3 个数 ai,bi,ci,表示物品的重量,利用价值,所属组数。
输出格式
一个数,最大的利用价值。
样例
1 2 3 4 5 6 7 Input 45 3 10 10 1 10 5 1 50 400 2 Output 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class bag { int tot; int [] w = new int [1010 ]; int [] v = new int [1010 ]; } public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int N = 0 ; bag[] a = new bag[1010 ]; int [] dp = new int [1010 ]; for (int i=1 ;i<=n;i++){ int x,y,z; x = sc.nextInt(); y = sc.nextInt(); z = sc.nextInt(); N = Math.max(N,z); if (a[z]==null ) a[z] = new bag(); a[z].tot++; a[z].w[a[z].tot]=x; a[z].v[a[z].tot]=y; } for (int i=1 ;i<=N;i++){ for (int j=m;j>=0 ;j--){ for (int k=1 ;k<=a[i].tot;k++){ if (j>=a[i].w[k]) dp[j] = Math.max(dp[j], dp[j-a[i].w[k]]+a[i].v[k]); } } } System.out.println(dp[m]); } }