第23章 基础背包问题
1、等和的分隔子集
算法分析
本身这题是一个dfs的题目，从1到n中枚举，有两种方法，要么放左边left，要么放右边right，最终枚举完时若left == right，则表示当前情况成立，ans ++，可是N = 39,2^39远大于10^8，因此直接dfs会直接gg掉，又由于枚举到当前状态x,left,right时，当前状态成立的方案数一定是固定的，因此可以用一个数组存储当前状态的值，空间换时间，于是采用记忆化搜索的方法
image.png
初始时，f[0][0][0] = 1;其他全是-1，为了方便排除方案数刚刚是0的情况(例如当n == 37时，就是方案数为0的情况)，由于N = 39，最大的累加和是(1 + 39) * 40 / 2 == 800，分成左右两个集合，因此每个集合最多是400，因此开f[40][400][400]的空间
注意：由于左右集和总和相等时可以看成等价，因此求出来的结果会产生重复，因此需要除以2
时间复杂度
远小于40 * 400 * 400
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 410;
static int n;
static int ans = 0;
static long[][][] f = new long[40][N][N];
static long dfs(int x,int left,int right)
{
if(f[x][left][right] != -1) return f[x][left][right];
f[x][left][right] = 0;
if(x <= 0) return f[x][left][right];
if(left - x >= 0) f[x][left][right] += dfs(x - 1,left - x,right);
if(right - x >= 0) f[x][left][right] += dfs(x - 1,left,right - x);
return f[x][left][right];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
int m = (1 + n) * n / 2;
for(int i = 0;i <= n;i ++)
for(int j = 0;j <= m / 2;j ++)
Arrays.fill(f[i][j], -1);
f[0][0][0] = 1;
System.out.println(dfs(n,m / 2,m / 2) / 2);
}
}
会超时的爆搜
时间复杂度)
Java 代码
import java.util.Scanner;
public class Main {
static int ans = 0;
static int n;
static void dfs(int x,int left,int right)
{
if(x == n + 1)
{
if(left == right) ans ++;
return ;
}
//放左边
dfs(x + 1,left + x,right);
//放右边
dfs(x + 1,left,right + x);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
dfs(1,0,0);
System.out.println(ans / 2);
}
}
2、饭卡
算法分析
贪心 + 01背包
在满足余额大于等于5且最后选一个物品的时候，尽可能选最贵的那个，因此所有菜式中最贵的那个一定必选，则变成了从剩余的1到n - 1个物品中选，总体积不超过m - 5的最大体积，则结果是总余额减去前n - 1个物品 再 减去最贵的那个物品，即m - f[m - 5] - a[n]
时间复杂度)
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 1010;
static int n,m;
static int[] a = new int[N];
static int[] f = new int[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
Arrays.sort(a,1,n + 1);
m = scan.nextInt();
for(int i = 1;i < n;i ++)
{
for(int j = m - 5;j >= a[i];j --)
{
f[j] = Math.max(f[j], f[j - a[i]] + a[i]);
}
}
System.out.println(m - f[m - 5] - a[n]);
}
}
3、offer
算法分析
01背包
每个学校都有一个成功的概率，映射成，每个学校都有一个失败的概率，例如
10 3
4 0.1 即 4 0.9
4 0.2 即 4 0.8
5 0.3 即 5 0.7
假设投资了某些学校，失败的概率分别是a1，a2,....ak，即成功的概率是1 - (a1 * a2 * ... * ak)，即相当于从前m个学校中选，总价格不超过n的失败概率的最小值
image.png
时间复杂度
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 10010;
static int n,m;
static double[] f = new double[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int m = Integer.parseInt(s1[0]);
int n = Integer.parseInt(s1[1]);
Arrays.fill(f, 1);
for(int i = 1; i <= n;i ++)
{
String[] s2 = br.readLine().split(" ");
int v = Integer.parseInt(s2[0]);
double w = 1 - Double.parseDouble(s2[1]);
for(int j = m;j >= v;j --)
{
f[j] = Math.min(f[j], f[j - v] * w);
}
}
System.out.printf("%.1f",(1 - f[m]) * 100);
System.out.println("%");
}
}
4、新年趣事之打牌
算法分析
01背包求方案数问题，以及求具体方案问题
注意的点：求方案数先开到long，背包的最大总体积是100 * 1000（100张牌，每张1000重量）
若方案数为1时，则从f[n,m]倒过来观察，若当前点是f[i,j]，若f[i,j]是由f[i - 1,j - v[i]]转移过来的，则走到f[i - 1,j - v[i]]，若f[i,j]是由f[i - 1,j]转移过来的，则走到f[i - 1,j]，并记录没用过的物品ans
时间复杂度
Java 代码
import java.util.Scanner;
public class Main {
static int N = 110,M = 100010;
static int n,m;
static long[][] f = new long[N][M];
static int[] v = new int[N];
static int[] ans = new int[N];
static int k = 0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
int n = scan.nextInt();
for(int i = 1;i <= n;i ++) v[i] = scan.nextInt();
f[0][0] = 1;
for(int i = 1;i <= n;i ++)
{
for(int j = 0;j <= m;j ++)
{
f[i][j] = f[i - 1][j];
if(j >= v[i])
f[i][j] += f[i - 1][j - v[i]];
}
}
if(f[n][m] > 1) System.out.println("-1");
else if(f[n][m] == 0) System.out.println("0");
else
{
int j = m;
for(int i = n;i >= 1;i --)
{
if(j >= v[i] && f[i][j] == f[i - 1][j - v[i]])
{
j -= v[i];
continue;
}
ans[k ++] = i;
}
for(int i = k - 1;i >= 0;i --)
{
if(i != 0) System.out.print(ans[i] + " ");
else System.out.println(ans[i]);
}
}
}
}
