动态规划和贪心算法都是一种递推算法，均用局部最优解来推导全剧最优解。
是对遍历解空间的一种优化
当问题具有最优子结构时，可用动态规划，而贪心算法是动态规划的特例。
8.1 贪心策略-----遵循某种规则，不断贪心的选取当前最优策略，最终找到最优解
-----难点：当前最优未必是全局最优
8.1.1 硬币问题有1，5，10，50，100，500元的硬币，各占c1, c5 , c10, c50, c100, c500枚
现在用这些硬币来支付A，最少需要多少枚硬币。
输入：
每一行有6个数字，代表不同硬币的个数
第二行为A，代表需要支付的A元
样例：
输入：
3 2 1 3 0 2
620
输出：
6
package 第八章_贪心算法和动态规划;
import java.util.Scanner;
public class 硬币支付问题 {
static int[] cnts = new int[6];
static int[] coins= {1,5,10,50,100,500};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < 6; i++) {
cnts[i] = scanner.nextInt();
}
int A = scanner.nextInt();
int res = f(A,5);
System.out.println(res);
}
private static int f(int A, int cur) {
// TODO Auto-generated method stub
if (A<=0) {
return 0;
}
if (cur == 0) {
return A;
}
int coinValue = coins[cur];
int x = A/coinValue;//金额中有多少个coinValue
int cnt = cnts[cur];//当前面值的硬币有cnt个
int t = Math.min(x, cnt);
return t+f(A-t*coinValue, cur-1);//用t个当前面值，剩下的继续处理。
}
}
8.1.2 快速渡河
题目：有N个人，跨越一条河，一艘船只能装2个人，两个人到对岸后，要划回来一个人，每个人划船速度不同。某一种排列可用使得总时间最少。
输入：1 4 1 2 5 10
输出：17
import java.util.Arrays;
import java.util.Scanner;
public class 快速渡河 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt(); //T组数据
for(int i=0;i0) {
if(left==1) { //只有一个人
ans+=speed[0];
break;
}else if(left==2) { //只有2人
ans+=speed[1];
break;
}
else if(left==3) { //有3个人
ans+=speed[2]+speed[0]+speed[1];
break;
}
else {
//1,2出发，1返回，最后两名出发，2返回
int s1=speed[1]+speed[0]+speed[left-1]+speed[1];
//1,3出发，1返回，1,4出发，1返回，1,2过河
int s2=speed[left-1]+speed[left-2]+2*speed[0]; //a+2b+c
ans+=min(s1,s2);
left-=2; //左侧是渡河起点，left代表左侧的剩余人数
}
}
System.out.println(ans);
}
private static int min(int s1, int s2) {
return 0;
}
}
8.1.3 区间调度问题
题目：不同时间段有不同的任务，我们要在规定时间内完成最多的任务，任务时间不能交叉，更不能重合。
选结束时间是最早的，才是最符合条件的。
输入：5 1 2 4 6 8 3 5 7 9 10
输出：3
package 第八章_贪心算法和动态规划;
import java.util.Arrays;
import java.util.Scanner;
public class 区间调度问题 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] s = new int[n];
int[] t = new int[n];
for (int i = 0; i < n; i++) {
s[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
t[i] = sc.nextInt();
}
Work[] works = new Work[n];
for (int i = 0; i < n; i++) {
works[i] = new Work(s[i], t[i]);
}
//将每个工作按照结束时间排序
Arrays.sort(works);
//首先完成结束时间最早的这项工作
int cut = 1; //计数器
int last = works[0].t; //存储每次工作之后的时间
for (int i = 1; i < n; i++) {
//每找到一个开始时间大于最后工作时间的工作，就去完成这项工作
if (works[i].s > last) {
cut ++;
last = works[i].t;
}
}
System.out.println(cut);
}
private static class Work implements Comparable {
int s;
int t;
public Work(int s, int t) {
this.s = s;
this.t = t;
}
@Override
public int compareTo(Work o) {
// TODO Auto-generated method stub
return this.t - o.t;
}
}
}
8.1.4 区间选点问题
题目：有多个不同的区间，他们有的交叉，有的包含。求最少的点数，使得其在所有的区间中。
和上一个题类似，选择区间结束最早的为第一个点。
给出n个闭整数区间[ai，bi]和n个整数C1，.，Cn。
编写一个程序：
从标准输入读取间隔的数目、它们的端点和整数c1、.、cn，
计算具有区间[ai，bi]的至少ci公共元素的整数集Z的最小大小，对于每一个i=1，2，.，n，
将答案写入标准输出。
输入：
输入的第一行包含整数n(1<=n<=50000)-间隔数。下面n行描述间隔。输入的(i+1)-第一行包含由单个空格分隔的三个整数ai、bi 和ci，使得0<=ai<=bi<=50000和1<=ci<=bi-ai+1。
输出：
输出包含一个整数，等于集合Z的最小大小，对于每一个i=1，2，.，n至少具有区间[ai，bi]的Ci元素。
样本输入：
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
样本输出
6
思路：
将所有区间按照bi从小到大排序，循环所有区间，从每个区间的bi处向前打点，在坐标轴上打点之前统计这个区间的需要的打点数，循环结束，打点器累加的值即为答案。
import java.util.Arrays;
import java.util.Scanner;
public class 区间选点问题 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Interval[] intervals = new Interval[n];
for (int i = 0; i < n; i++) {
intervals[i] = new Interval(sc.nextInt(), sc.nextInt(), sc.nextInt());
}
Arrays.sort(intervals);// 按区间右端点排序
int max = intervals[n - 1].t;// 右端最大值
int[] axis = new int[max + 1];// 标记数轴上的点是否已经被选中
// int[] sums = new int[max + 1];
for (int i = 0; i < n; i++) {
// 1.查阅区间中有多少个点
int s = intervals[i].s;// 起点
int t = intervals[i].t;// 终点
int cnt = sum(axis, s, t);// 找到这个区间已经选点的数量，
//sums[t] - sums[s - 1]; 效率低
// 2.如果不够，从区间右端开始标记，遇标记过的就跳过
intervals[i].c -= cnt;// 需要新增的点的数量
while (intervals[i].c > 0)
if (axis[t] == 0) {// 从区间终点开始选点
axis[t] = 1;
// updateSums(t,sums);//更新前缀和
intervals[i].c--;// 进一步减少需要新增的点的数量
t--;
} else {// 这个点已经被选过了
t--;
}
}
}
System.out.println(sum(axis, 0, max));
}
private static int sum(int[] axis, int s, int t) {
int sum = 0;
for (int i = s; i <= t; i++) {
sum += axis[i];
}
return sum;
}
private static void updateSums(int t, int[] sums) {
for (int i = t; i < sums.length; i++) {
sums[i]++;
}
}
private static class Interval implements Comparable {
int s;
int t;
int c;
public Interval(int s, int t, int c) {
this.s = s;
this.t = t;
this.c = c;
}
@Override
public int compareTo(Interval other) {
int x = this.t - other.t;
if (x == 0)
return this.s - other.s;
else
return x;
}
}
8.1.4 字典序最小问题
题目：给一个定长为N的字符串S，构造一个字符串T，长度也为N。
起初，T是一个空串，随后反复进行下列任意 *** 作
1、从S的头部删除一个字符，加到T的尾部。
2、从S的尾部删除一个字符，加到T的头部。
目标是最后生成的字符串T的字典序尽可能小。
输入：字符串S ACDBCB
输出：字符串T ABCBCD
每次选开头和结尾较大者放入新的字符串的末尾，不过需要注意的是，当首尾相同时需要比较前后的下一个（即左边的右边一个和右边的左边一个）的大小，下一个是较小的那个放入新的字符串。
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String str = "";
for(int i = 0;i < n;i++) {
str += sc.next();
}
char ch[] = str.toCharArray();
int begin = 0;
int end = ch.length-1;
int count = 0;
while(begin <= end) {
boolean flag = false;
for(int i = 0;i+begin <= end;i++) {
if(ch[begin+i] < ch[end-i]) {
flag = true;
count++;
break;
}
else {
flag = false;
count++;
break;
}
}
if(flag) {
System.out.print(ch[begin++]);
}
else {
System.out.print(ch[end--]);
}
if(count%80==0) {
System.out.println();
}
}
System.out.println();
sc.close();
}
}
8.1.5 最优装载问题
题目:给定 N 个物体，第 i 个物体的质量为 Wi ,选择尽量多的物体，使其总量不超过C。
import java.util.Arrays;
public class LoadingProblem {
private static int[] x;
public static float Loading(float c, float[] w, int[] x) {
int n = w.length;
Element[] d = new Element[n];
for (int i = 0; i < n; i++) {
// 初始化
d[i] = new Element(w[i], i);
}
Arrays.sort(d);
// 记录最优值
float opt = 0;
for (int i = 0; i < n; i++) {
// 初始化
x[i] = 0;
}
for (int i = 0; i < n && d[i].w <= c; i++) {
x[d[i].i] = 1;
opt += d[i].w;
c -= d[i].w;
}
return opt;
}
public static void main(String[] args) {
float c = 10;
float[] w = new float[]{4, 2, 5, 1, 3};
x = new int[w.length];
float opt = Loading(c, w, x);
System.out.println("最优值为: " + opt);
System.out.println("最优解为： " + Arrays.toString(x));
}
public static class Element implements Comparable {
float w;
int i;
public Element(float w, int i) {
this.w = w;
this.i = i;
}
@Override
public int compareTo(Element o) {
if (this.w < o.w)
return -1;
else if (this.w == o.w)
return 0;
else
return 1;
}
}
}
8.1.6 乘船问题
题目：有N个人，第i个人的重量为 Wi ，每艘船的最大载重为C，且最多只能乘两个人。用最少的船装载所有的人。
贪心策略：考虑最轻的人，如果每个人都无法与他一起坐船，则唯一的方案是每个人做一艘，否则，他应该选择能和他一起坐船的人中最中的那个。
import java.util.Arrays;
import java.util.Scanner;
public class 乘船问题 {
//乘船问题
//有n个人，第i个人重量为wi。每艘船的最大载重量均为C，
// 且最多只能乘两个人。用最少的船装载所有人。
public static int solve(int []w,int C)
{
int n=w.length;//人数
int st=0;//定义开始和结束指针
int et=w.length-1;
int out=0;//要返回的船只的个数
while(n>0)
{
if (w[st]>=C)//若最小的人的重量大于C
{
out=w.length;
break;
}
if (w[st]+w[et]<=C)//若开始和结束的重量小于C
{
out++;
n-=2;
st++;
et--;
}
else//若开始和结束的重量大于C
{
out++;
et--;
n--;
}
}
return out;
}
public static void main(String[] args) {
Scanner a=new Scanner(System.in);
int n=a.nextInt();//输入人数n
int []w=new int[n];//输入每个人的重量
for (int i = 0; i
8.2 动态规划
动态规划方法代表了这一类问题(最优子结构 || 子问题的最优性 || 重叠子问题 ) 的一般解法，是设计方法或者策略，不是具体算法。
本质是递推，核心是找到状态转移的方式，写出dp方程
形式：
记忆性递归
递推
8.2.1 01背包问题
有N个重量和价值分别为 Wi ，Vi，的物品，从这些物品中挑选出纵质量不超过W的物品。求所有挑选方案中的价值总和最大值。
输入：
n = 4
(w,v) = {(2,3),(1,2),(3,4),(2,2)}
W = 5
输出：
7（选择0 1 3号物品）
因为对每个物品只有选和不选两种情况，所以成为01规划问题
f (i, j) : 当背包容量为 J ， 挑出 i 件商品的最大价值。
题目即求：f(4，5)
import java.util.*;
public class 01背包问题{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int number = sc.nextInt(); // 物品的数量
// 注意：我们声明数组的长度为"n+1",并另score[0]和time[0]等于0。
// 从而使得 数组的下标，对应于题目的序号。即score[1]对应于第一题的分数,time[1]对应于第一题的时间
int[] weight = new int[number + 1]; // {0,2,3,4,5} 每个物品对应的重量
int[] value = new int[number + 1]; // {0,3,4,5,6} 每个物品对应的价值
weight[0] = 0;
for (int i = 1; i < number + 1; i++) {
weight[i] = sc.nextInt();
}
value[0] = 0;
for (int i = 1; i < number + 1; i++) {
value[i] = sc.nextInt();
}
int capacity = sc.nextInt(); // 背包容量
int[][] v = new int[number + 1][capacity + 1];// 声明动态规划表.其中v[i][j]对应于：当前有i个物品可选，并且当前背包的容量为j时，我们能得到的最大价值
// 填动态规划表。当前有i个物品可选，并且当前背包的容量为j。
for (int i = 0; i < number + 1; i++) {
for (int j = 0; j < capacity + 1; j++) {
if (i == 0) {
v[i][j] = 0; // 边界情况：若只有0道题目可以选做，那只能得到0分。所以令V(0,j)=0
} else if (j == 0) {
v[i][j] = 0; // 边界情况：若只有0分钟的考试时间，那也只能得0分。所以令V(i,0)=0
} else {
if (j < weight[i]) {
v[i][j] = v[i - 1][j];// 包的容量比当前该物品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
} else {
v[i][j] = Math.max(v[i - 1][j], v[i - 1][j - weight[i]] + value[i]);// 还有足够的容量可以装当前该物品，但装了当前物品也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
}
}
}
}
System.out.println();
System.out.println("动态规划表如下：");
for (int i = 0; i < number + 1; i++) {
for (int j = 0; j < capacity + 1; j++) {
System.out.print(v[i][j] + "t");
}
System.out.println();
}
System.out.println("背包内最大的物品价值总和为：" + v[number][capacity]);// 有number个物品可选，且背包的容量为capacity的情况下，能装入背包的最大价值
int[] item = new int[number + 1];// 下标i对应的物品若被选中，设置值为1
Arrays.fill(item, 0);// 将数组item的所有元素初始化为0
// 从最优解，倒推回去找
int j = capacity;
for (int i = number; i > 0; i--) {
if (v[i][j] > v[i - 1][j]) {// 在最优解中，v[i][j]>v[i-1][j]说明选择了第i个商品
item[i] = 1;
j = j - weight[i];
}
}
System.out.print("包内物品的编号为：");
for (int i = 0; i < number + 1; i++) {
if (item[i] == 1) {
System.out.print(i + " ");
}
}
System.out.println("----------------------------");
}
}
}
8.2.2 钢条切割
Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。
假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。
| 长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
价格pi | 1 | 5 | 8 | 16 | 10 | 17 | 17 | 20 | 24 | 30 |
import java.util.Scanner;
import static java.lang.Math.max;
public class 钢条切割{
static int rec[];
public static void main(String[] args) {
//下面使用动态规划来进行解决,关键是要求出变化的量在哪里,我们可以使用excel表格来进行打表帮助我们更好地理解
//以便求出最佳的切割方案
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int v[] = new int[n];
for(int i = 0; i < n; i++){
v[i] = sc.nextInt();
}
dp(v, n);
sc.close();
}
private static void dp(int[] v, int n){
rec = new int[n + 1];
for(int i = 1; i < n + 1; i++){
for(int j = 1; j <= i; j++){
//前面的是保留的是整对的长度,后面的是需要切割钢条的剩余长度的最佳切割方案
rec[i] = max(v[j - 1] + rec[i - j], rec[i]);
}
}
System.out.println(rec[n]);
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）