九章算法笔记D5-背包型动态规划

@[toc]

D5 背包型动态规划

Backpack I

Problem:

给定N个物品,重量分别为正整数A0,A1,...,AN-1,一个背包最大承重是正整数M,最多能带走多重的物品

样例 :

1
2
输入: 4个物品,重量为2,3,5,7。背包最大承重是11
输出: 10(三个物品:2,3,5)

确定状态:

  1. 如果前N-1个物品能拼出W,当然前N个物品也能拼出W
  2. 如果前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)]

  1. 能否用前i个物品拼出重量w
  2. 能否用前i-1个物品拼出重量w
  3. 能否用前i-1个物品拼出重量w-A(i-1),再加上第i个物品

初始条件:

  1. f[0][0] = TRUE:0个物品可以拼出重量0
  2. 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];
//pi[i][j] = 0 : not use the item
//pi[i][j] = 1 : use the item
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];
//initialize
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];//注意为什么减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)]

  1. 用前i个物品有多少种方式拼出重量w
  2. 用前i-1个物品有多少种方式拼出重量w
  3. 用前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][0] = 1,f[0][1]=f[0][2]...=0
f[0] = 1;
for (i = 1; i <= m; i++) {
f[i] = 0;
}
for (i = 1; i <= n; i++) {
//reverse order!
for (j = m; j >= 0; j--) {
if (j >= A[i - 1]) {//防止越界
//old + old ==> new
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)

分析

  1. 任何一个正确的组合中,所有物品总重量是Target
  2. 如果最后一个物品重量是K,则前面的物品重量是Targert-K

转移方程:

设f[i] = 有多少种组合能拼出重量 i f[i]=f[i-A0]+f[i-A1]+...+f[i-A(N-1)]

  1. 多少种组合能拼出i
  2. 多少种组合能拼出i-A0
  3. 多少种组合能拼出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
/*用一维数组来表示
题目:采药
链接:https://vijos.org/p/1104
*/
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--){//注意不能从t到0,否则j-w[i]可能会越界
dp[j] = Math.max(dp[j],dp[j-w[i]]+val[i]);
}
}
System.out.println(dp[t]);
}
}
/*甚至val数组和w数组都不用开*/
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--){//注意不能从t到0,否则j-w[i]可能会越界
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
//原题:疯狂的采药 链接:luogu.com.cn/problem/P1616
//完全背包模板
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++) {//刚好跟01背包相反
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)//如果为0则直接返回
return;
int f[n+1][b+1],I[n+1][b+1];//f表示备忘录数组,I表示标记函数
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++){//物品数量从1,到前n
for(int j=0;j<=b;j++){//j表示背包容量从0到b
f[i][j]=f[i-1][j];//用于比较 max(f[i-1][j],f[i][j-W[i-1]]+V[i-1])
I[i][j]=I[i-1][j];//用于记录选择
if(j>=W[i-1]&&f[i][j]<=f[i][j-W[i-1]]+V[i-1]){// j>=W[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];//定义x来存放最后拿取各个物品的数量
for(int j=1;j<=n;j++){
x[j]=0;//初始化
}
int y = b,j=n;//y表示背包容量,j表示物品数量
do{
j = I[j][y];//第一次表示优化函数的最后一行的最后一列
x[j]=1;//当前的j至少有1个
y = y-W[j-1];//y应该减去相应的物品重量
while(I[j][y]==j){//如果I[j][y]还等于j时
y = y-W[j-1];//y应该减去相应的物品重量
x[j] = x[j]+1;//物品数量+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++){
//f[i][j-A[i-1]]
if(w>=W[i-1]&&f[w-W[i-1]]!=-1){//注意此时是f[i][w-A[i-1]]与II的区别
f[w] = max(f[w],f[w-W[i-1]]+V[i-1]);
//now f[j] is f[i][j]
}
}
}
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小结

  1. Backpack 可行性 背包
    • 要求不超过Target时能拼出的最大重量
    • 记录前i个物品能不能拼出重量w
  2. Backpack V,Backpack VI,计数型 背包
    • 要求有多少种方式拼出重量Target
    • Backpack V:记录前i个物品有多少种方式拼出重量w
    • Backpack VI:记录有多少种方式拼出重量w
  3. BackpackII,BackpackIII,最值型 背包
    • 要求能拼出最大价值
    • 记录f[i][w] = 前 i 个/种 物品能拼出重量w能得到的最大价值
  4. 关键点
    • 最后一步:
      • 最后一个背包内的物品是哪个
      • 最后一个物品有没有进背包
    • 数组大小和最大承重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
2
4 4
1 1 2 2

输出 #1

1
3
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
Input
11
Output
9
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--){//套用01背包模板
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++) {//无法在上面循环中直接判断,因为需要从1到m来判断第一个比v大的位置
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
Input
7
Output
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
//问题转换:能否在1-n的数中拼出(1+n)*n/2
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]; // + j
}
}
System.out.println(dp[m / 2] / 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--){//由于判断需要到k,所以直接枚举到0在进行判断
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]);//套用01背包模板
}
}
}
System.out.println(dp[m]);
}
}

2020年7月9日更