动态规划的用法——01背包问题

最后更新于：2022-04-01 20:19:56

动态规划的用法——01背包问题

问题主题：著名的01背包问题

问题描述：

有n个重量和价值分别为wi、vi的物品，现在要从这些物品中选出总重量不超过W的物品，求所有挑选方案中的价值最大值。

限制条件：

1<=N<=100

1<=wi 、vi<=100

1<=wi<=10000

样例：

输入

N=4

W[N] = {2, 1, 3, 2}

V[N] = {3, 2, 4, 2}

输出

W = 5(选择0，1，3号)

### 【解法一】 ### 解题分析：用普通的递归方法，对每个物品是否放入背包进行搜索 ### 程序实现: **C++**

#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"
 
using namespace std;
 
const int N = 4;
const int W = 5;
int weight[N] = {2, 1, 3, 2};
int value[N] = {3, 2, 4, 2};
int solve(int i, int residue) 
{
int result = 0;
if(i >= N)
return result;
if(weight[i] > residue)
result = solve(i+1, residue);
else 
{
result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]);
}
 
}
 
int main() {
int result = solve(0, W);
cout << result << endl;
return 0;
}

**** ### 【解法二】 ### 解题分析：用记录结果再利用的动态规划的方法，上面用递归的方法有很多重复的计算，效率不高。我们可以记录每一次的计算结果，下次要用时再直接去取，以提高效率 ### 程序实现: **C++**

#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"

using namespace std;

const int N = 4;
const int W = 5;
int weight[N] = {2, 1, 3, 2};
int value[N] = {3, 2, 4, 2};
int record[N][W];
void init()
{
	for(int i = 0; i < N; i ++)
	{
		for(int j = 0; j < W; j ++) 
		{
			record[i][j] = -1;
		}
	}
}

int solve(int i, int residue) 
{
	if(-1 != record[i][residue])
		return record[i][residue];
	int result = 0;
	if(i >= N)
		return result;
	if(weight[i] > residue)
	{
		record[i + 1][residue] = solve(i+1, residue);
		
	}
	else 
	{
		result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]);
	}
	return record[i + 1][residue] = result;
}

int main() {
	init();
	int result = solve(0, W);
	cout << result << endl;
	return 0;
}

**Java**

package greed;

/**
 * User: luoweifu
 * Date: 14-1-21
 * Time: 下午5:13
 */
public class Knapsack {
	private int maxWeight;
	private int[][] record;
	private Stuff[] stuffs;

	public Knapsack(Stuff[] stuffs, int maxWeight) {
		this.stuffs = stuffs;
		this.maxWeight = maxWeight;
		int n = stuffs.length + 1;
		int m = maxWeight+1;
		record = new int[n][m];
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
				record[i][j] = -1;
			}
		}
	}
	public int solve(int i, int residue) {
		if(record[i][residue] > 0) {
			return record[i][residue];
		}
		int result;
		if(i >= stuffs.length) {
			return 0;
		}
		if(stuffs[i].getWeight() > residue) {
			result = solve(i + 1, residue);
		} else {
			result = Math.max(solve(i + 1, residue),
				 solve(i + 1, residue - stuffs[i].getWeight()) + stuffs[i].getValue());
		}
		record[i][residue] = result;
		return result;
	}

	public static void main(String args[]) {
		Stuff stuffs[] = {
			new Stuff(2, 3),
			new Stuff(1, 2),
			new Stuff(3, 4),
			new Stuff(2, 2)
		};
		Knapsack knapsack = new Knapsack(stuffs, 5);
		int result = knapsack.solve(0, 5);
		System.out.println(result);
	}
}

class Stuff{
	private int weight;
	private int value;

	public Stuff(int weight, int value) {
		this.weight = weight;
		this.value = value;
	}

	int getWeight() {
		return weight;
	}

	void setWeight(int weight) {
		this.weight = weight;
	}

	int getValue() {
		return value;
	}

	void setValue(int value) {
		this.value = value;
	}
}

**** ### 算法复杂度：时间复杂度O(NW)

';

贪心算法——字典序最小问题

最后更新于：2022-04-01 20:19:53

贪心算法——字典序最小问题

问题主题：字典序最小

问题描述：

给定长度为N的字符串S，要构造一个长度为N字符串T。T是一个空串，反复执行下列任意操作：

l 从S的头部删除一个字符，加到T的尾部；

l 从S的尾部删除一个字符，加到T的尾部；

目标是要构造字典序尽可能小的字符串T。

限制条件：

1<=N<=2000

字符串都在大写字符

样例：

输入

N=8

ADHCACBD

输出

ADBCACDH

### 解题分析：看到这个问题，首先你肯定不难想到：**每次都从**S的头部或尾部选择最小的字符放到T的尾部** 对，这已经很接近真实了，但是还没考虑首部和尾部相同的情况，那么首部和尾部相同的情况下该取首部还是尾部呢？其实思路还是一样的，如果首部A和尾部B相同，就取首部的下一个字符(也就是第2个字符，设为A’)和尾部的前一个字符(也就量倒数第2个字符，设为B’)比较，如果A’

#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"

using namespace std;

const int N = 8;
char chs[N+1] = "ADHCACBD";

char* solve(char chs[])
{
	int start = 0, end = N - 1;
	bool isLeft = false;
	char dest[N];
	while(start <= end) {
		for(int i = 0; start + i < end; i ++)
		{
			if(chs[start + i] < chs[end - i]) 
			{
				isLeft = true;
				break;
			}
				
			else if(chs[start + i] > chs[end -i])
			{
				isLeft = false;
				break;
			}
			else 
				continue;
		}
		if(isLeft)
		{
			dest[N-(end - start + 1)] = chs[start ++];
			//putchar(chs[start ++]);
		}
		else
		{
			dest[N-(end - start + 1)] = chs[end --];
			//putchar(chs[end --]);
		}
	}
	
	return dest;
}

int main() {
	char *result = solve(chs);
	for(int i=0; i<N; i++) 
	{
		putchar(result[i]);
	}
	return 0;
}

**Java**

package greed;

/**
 * User: luoweifu
 * Date: 14-1-20
 * Time: 上午9:41
 */
public class BestCowLine {
	public static String cowLine(String s) {
		char[] chs = new char[s.length()];
		char[] dest = new char[s.length()];
		s.getChars(0, s.length(), chs, 0);
		int start = 0, end = s.length() - 1;
		while(start <= end) {
			boolean isLeft = false;
			for(int i=0; i <= end - start; i++) {
				if(chs[start + i] < chs[end - i]) {
					isLeft = true;
					break;
				} else if(chs[start + i] > chs[end - i]) {
					isLeft = false;
					break;
				}
			}
			if(isLeft) {
				dest[s.length() - (end - start + 1)] = chs[start ++];
			} else {
				dest[s.length() - (end - start + 1)] = chs[end --];
			}
		}
		return new String(dest);
	}

	public static void main(String args[]) {
		System.out.println(cowLine("ADHCACBD"));
	}

}

**** ### 算法复杂度：时间复杂度O(n(1+n)/2) = O(n2)

';

贪心算法——区间调度问题

最后更新于：2022-04-01 20:19:51

贪心算法——区间调度问题

问题主题：区间调度问题

问题描述：

有n项工作，每项工作分别在si开始，ti结束。对每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与，即参与工作的时间段不能有重叠(即使开始的时间和结束的时间重叠都不行)。

限制条件：

1<=n<=100000

1<=si<=ti,=109

样例：

输入

n=5

s={1,2,4,6,8}

T={3,5,7,9,10}

输出

3(选择工作1, 3, 5)

### 解题分析：对这个问题，如果使用贪心算法的话，可能有以下几种考虑： (1)、每次选取开始时间最早的； (2)、每次选取结束时间最早的； (3)、每次选取用时最短的； (4)、在可选工作中，每次选取与最小可选工作有重叠的部分；对于上面的四种算法，只有算法(2)是正确的，其它的三种都可以找到相应的反例。具体证明如下：数轴上有n个区间，选出最多的区间，使得这些区间不互相重叠。 **算法：** 将所有区间按右端点坐标从小到大排序，顺序处理每个区间。如果它与当前已选的所有区间都没有重叠，则选择该区间，否则不选。 **证明：** 显然，该算法最后选出的区间不互相重叠，下面证明所选出区间的数量是最多的。设fi为该算法所接受的第i个区间的右端点坐标，gi为某最优解中的第i个区间的右端点坐标。 **命题1.1** 当**i>=1**时，该算法所接受的第**i**个区间的右端点坐标**f**i**<=**某最优解中的第**i**个区间的右端点坐标**gi**。**** 该命题可以运用数学归纳法来证明。对于i=1，命题显然为真，因为算法第一个选择的区间拥有最小右端点坐标。令i>1，假定论断对i-1为真，即fi-1<=gi-1。则最优解的第i个可选区间所组成的集合包含于执行该算法时第i个可选区间所组成的集合；而当算法选择第i个区间时，选的是在可选区间中右端点坐标最小的一个，所以有fi<=gi。证毕。设该算法选出了k个区间，而最优解选出了m个区间。 **命题1.2** 最优解选出的区间数量**m=**该算法选出的区间数量**k**。**** 假设m>k，根据命题1.1，有fk<=gk。由于m>k，必然存在某区间，在gk之后开始，故也在fk之后开始。而该算法一定不会在选了第k个区间后停止，还会选择更多的区间，产生矛盾。所以m<=k,又因为m是最优解选出区间个数，所以m=k。综上所述，算法选出的区间是最优解。 ### 程序实现: **C++**

#include <stdio.h>

#include <tchar.h>

#include <queue>

#include "iostream"

using namespace std;

const int N = 5;

int s[N]={1,2,4,6,8};

int t[N]={3,5,7,9,10};

int solve()

{

pair<int, int> itv[N];

for(int i = 0; i < N; i ++) {

itv[i].first = s[i];

itv[i].second = t[i];

}

sort(itv, itv + N);

int count = 0;

int t = 0;

for(int i = 0; i < N; i ++) {

if(t < itv[i].first) {

count ++;

t = itv[i].second;

}

return count;

}

int main() {

cout << solve() << endl;

return 0;

}

**Java**

package greed;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: shihuichao
 * Date: 14-1-14
 * Time: 下午10:43
 * To change this template use File | Settings | File Templates.
 */
public class Interval {
	public static int interval(Work[] works) {
		Arrays.sort(works);
		int count = 0;
		//当前工作的结束时间
		int t = 0;
		for (int i = 0; i < works.length; i++) {
			if(t < works[i].getStart()) {
				count ++;
				t = works[i].getTerminate();
			}
		}
		return count;
	}

	public static void main(String args[]) {
		Work[] works = {
			new Work(1, 3),
			new Work(2, 5),
			new Work(4, 7),
			new Work(6, 9),
			new Work(8, 10)
		};
		int result = interval(works);
		System.out.println(result);
	}
}

class Work implements Comparable {
	private int start;
	private int terminate;

	Work(int start, int terminate) {
		this.start = start;
		this.terminate = terminate;
	}

	int getStart() {
		return start;
	}

	void setStart(int start) {
		this.start = start;
	}

	int getTerminate() {
		return terminate;
	}

	void setTerminate(int terminate) {
		this.terminate = terminate;
	}

	@Override
	public int compareTo(Object o) {
		Work work = (Work) o;
		if (this.terminate > work.getTerminate())
			return 1;
		else if (this.terminate == work.getTerminate())
			return 0;
		else
			return -1;
	}
}

**** ### 算法复杂度：时间复杂度 On(nlogn) = 排序O(nlogn) + 扫描O(n)

';

贪心算法——找纸币问题

最后更新于：2022-04-01 20:19:49

贪心算法——找纸币问题

问题主题：找钱

问题描述：

假设有1元、2元、5元、10元、20元、50元、100的纸币分别为c0, c1, c2, c3, c4, c5, c6,张。现在要用这些钱来支付K元，至少要用多少张纸币？如果能找，则输出纸币的张数，不能找则输出No

限制条件：

0<=c0, c1,c2,c3,c4,c5,c6<=109

0<=K<=109

样例：

输入

C0=3, c1=0, c2=2, c3=1, c4=0, c5=3, c6=5

输出

6

### 【解法一】 ### 解题分析：本题使用贪心算法，只需要考虑“尽可能多地使用面值大的纸币”，然后根据面值的大小从大到小排序依次选择。 ### 程序实现: **C++**

#include "iostream"

using namespace std;

const int N = 7;

static int K = 6200;

int min(int num1, int num2);

int momeyCount[N] = {3, 0, 2, 1, 0, 3, 5};

int value[N] = {1, 2, 5, 10, 20, 50, 100};

int giveChange() {

int num = 0;

for(int i = N-1; i >= 0; i --) {

int c = min(K/value[i], momeyCount[i]);

K = K - c * value[i];

num += c;

}

if(K > 0)

num = -1;

return num;

}

int min(int num1, int num2) {

return num1 < num2 ? num1 : num2;

}

int main() {

int result = giveChange();

if(result != -1)

cout << result << endl;

else

cout << "NO" << endl;

return 0;

}

**Java** ~~~ package greed; import java.util.Arrays; /** * 找钱问题 * User: luoweifu * Date: 14-1-14 * Time: 下午8:08 */ public class GiveChange { public static int gaiveChange(MoneyBox[] moneyBoxes, int target) { Arrays.sort(moneyBoxes); int count = 0; for(int i = moneyBoxes.length-1; i >= 0; i--) { int currentCount = Math.min(moneyBoxes[i].getCount(), target/moneyBoxes[i].getValue()); target -= currentCount*moneyBoxes[i].getValue(); count += currentCount; } if(target > 0) { count = -1; } return count; } public static void main(String args[]) { MoneyBox[] moneyBoxes = { new MoneyBox(1, 3), new MoneyBox(2, 0), new MoneyBox(5, 2), new MoneyBox(10, 1), new MoneyBox(20, 0), new MoneyBox(50, 3), new MoneyBox(100, 5), }; int result = gaiveChange(moneyBoxes, 620); if(result > 0) System.out.println(result); else System.out.println("No"); } } /** * 钱盒子 */ class MoneyBox implements Comparable{ private int value; private int count; MoneyBox(int value, int count) { this.value = value; this.count = count; } int getValue() { return value; } void setValue(int value) { this.value = value; } int getCount() { return count; } void setCount(int count) { this.count = count; } @Override public int compareTo(Object o) { MoneyBox moneyBox = (MoneyBox)o; if(this.value < moneyBox.getValue()) return -1; else if(this.value == moneyBox.getValue()) return 0; else return 1; } } ~~~ **** ### 算法复杂度：时间复杂度:如果纸币已经排序(如C++代码)，O(n);如果纸币未经排序 (如Java代码)，O(nlogn);

';

深度优先搜索的用法——lake counting

最后更新于：2022-04-01 20:19:47

深度优先搜索的用法——lake counting

问题主题：Lake Counting

问题描述：

有一个大小为N*M的园子，雨后积了很多水。八连通的积水被认为是在一起的。请求出园子里共有多少个水洼？(八连通是指下图中相对+的*部分)

+++

+*+

+++

限制条件：

N,M <= 100

样例：

输入

N=10, M=12

园子如下图(‘+’表示积水，’*’表示没有积水)

+****++*

*+++***+++

**++***++*

*****++*

*****+**

**+****+**

*+*+***++*

+*+*+***+*

*+*+****+*

**+*****+*

输出

3

### 【解法一】 ### 解题分析：从任意的’+’开始，不停地把邻接的部分用’*’代替，一次dfs(深度优先遍历)遍历后，与初始的这个+所连接的所有+都会被替换成*，因此直到图中没有+为止，总共进行dfs的次数即为积水的次数。 ### 程序实现: **C++**

#include "iostream"

using namespace std;

const int N = 10;

const int M = 12;

char garden[N][M+1] = {

"+****++*",

"*+++***+++",

"**++***++*",

"*****++*",

"*****+**",

"**+****+**",

"*+*+***++*",

"+*+*+***+*",

"*+*+****+*",

"**+*****+*"

};

void dfs(int x, int y);

void solve() {

int count = 0;

for(int j=0; j<N; j++) {

for(int i=0; i<M; i++){

if(garden[j][i] == '+') {

dfs(j, i);

count ++;

}

cout << count << endl;

}

void dfs(int y, int x) {

garden[y][x] = '*';

for(int dy=y-1; dy<=y+1; dy++) {

for(int dx=x-1; dx<=x+1; dx++) {

if(dx >=0 && dy >= 0 && dx < M && dy < N && garden[dy][dx] == '+') {

dfs(dy, dx);

}

int main() {

solve();

return 0;

}

**Java**

/**
 * User: luoweifu
 * Date: 14-1-7
 * Time: 下午4:53
 */
public class LakeCounting {
public static final int N = 10;
public static final int M = 12;
private String garden[] = {
"+****++*",
"*+++***+++",
"**++***++*",
"*****++*",
"*****+**",
"**+****+**",
"*+*+***++*",
"+*+*+***+*",
"*+*+****+*",
"**+*****+*"
};
 
public void solve() {
int count = 0;
for(int j=0; j<N; j++) {
for(int i=0; i<M; i++){
if(garden[j].charAt(i) == '+') {
dfs(j, i);
count ++;
}
}
}
System.out.println(count);
}
 
public void dfs(int y, int x) {
StringBuilder stringY = new StringBuilder(garden[y]);
stringY.setCharAt(x, '*');
garden[y] = stringY.toString();
for(int dy=y-1; dy<=y+1; dy++) {
for(int dx=x-1; dx<=x+1; dx++) {
if(dx >=0 && dy >= 0 && dx < M && dy < N && garden[dy].charAt(dx) == '+') {
dfs(dy, dx);
}
}
}
}
 
public static void main(String args[]) {
LakeCounting lakeCounting = new LakeCounting();
lakeCounting.solve();
}
}

';

深度优先搜索的用法——求数组部分和

最后更新于：2022-04-01 20:19:44

**深度优先搜索的用法——求数组部分和**

问题主题：求数组部分和

问题描述：

给定整数a1,a2, … an，判断能否从中选出若干个数，使得它们的和为k。

限制条件：

1<=n<=20

-10⁸<=a_i<=10⁸

-10⁸<=k<=10⁸

样例：

输入

n=4

a={1,2,4,7}

k=13

输出

Yes (13=2+4+7)

输入

n=4

a={1,2,4,7}

k=15

输出

No

### 【解法一】 ### 解题分析：用递归的方法实现深度优先搜索，从a0开始依次判断，决定ai加入或不加入，对每一个种组合进行判断，决定是否存在和为k的情况。 ### 程序实现: **C++**

#include "stdafx.h"

#include "iostream"

using namespace std;

const int MAX = 10;

int result;

int a[MAX];

int sum = 0;

bool resolve(int a[], int n, int i, int sum) ;

int _tmain(int argc, _TCHAR* argv[]) {

int n;

cout << "请?输º?入¨?n和¨ª结¨¢果?的Ì?大ä¨®小?:" <<endl;

cin >> n >> result;

cout << "请?输º?入¨?n个?数ºy:" <<endl;

for(int i=0; i<n; i++) {

cin >> a[i];

}

if(resolve(a, n, 0, sum))

cout << "Yes" <<endl;

else

cout << "No" << endl;

return 0;

}

bool resolve(int a[], int n, int i, int sum) {

if(i >= n)

return sum == result;

//不?选?a[i]

if(resolve(a, n, i+1, sum))

return true;

//加¨®上¦?a[i]

if(resolve(a, n, i+1, sum+a[i]))

return true;

return false;

}

**Java**

/**
 * User: luoweifu
 * Date: 14-1-7
 * Time: 上午11:33
 */
public class PartSum {
    private int array[];
    private int result;
    public PartSum() {
 
    }
 
    public PartSum(int[] array, int result) {
        this.array = array;
        this.result = result;
    }
 
       public void setArray(int[] array) {
              this.array = array;
       }
 
       public void setResult(int result) {
              this.result = result;
       }
 
       public boolean resolve(int[] array, int i, int sum) {
              int n = array.length;
              if(i >= n)
                     return sum == result;
              if(resolve(array, i+1, sum))
                     return true;
              if(resolve(array, i+1, sum+array[i]))
                     return true;
              return false;
       }
 
       public void partsumResolve() {
              if(resolve(array, 0, 0))
                     System.out.println("Yes");
              else
                     System.out.println("No");
       }
 
       public static void main(String args[]) {
              PartSum partSum = new PartSum(new int[]{1,2,4,7}, 13);
              partSum.partsumResolve();
              partSum.setResult(15);
              partSum.partsumResolve();
       }
 
}

**** ### 算法复杂度：时间复杂度O(2n)

';

c++实现二分查找

最后更新于：2022-04-01 20:19:42

# 简要描述 **二分查找**又称折半查找，对排好序的数组，每次取这个数和数组中间的数进行比较，复杂度是O(logn)如:设数组为a[n],查找的数x, 如果x==a[n/2]，则返回n/2; 如果x < a[n/2]，则在a[0]到a[n/2-1]中进行查找；如果x > a[n/2]，则在a[n/2+1]到a[n-1]中进行查找； **优点**是比较次数少，查找速度快，平均性能好；其**缺点**是要求待查表为有序表，且插入删除困难。条件：**查找的数组必须要为有序数组。** # 二种实现方式 ### 1.递归 ~~~ /* 归的二分查找 arrat：数组， low:上界； high:下界; target:查找的数据；返回target所在数组的下标 */ int binarySearch(int array[], int low, int high, int target) { int middle = (low + high)/2; if(low > high) { return -1; } if(target == array[middle]) { return middle; } if(target < array[middle]) { return binarySearch(array, low, middle-1, target); } if(target > array[middle]) { return binarySearch(array, middle+1, high, target); } } ~~~ ### 2.非递归（循环） ~~~ /* 非递归的二分查找 arrat：数组， n:数组的大小; target:查找的数据；返回target所在数组的下标 */ int binarySearch2(int array[], int n, int target) { int low = 0, high = n, middle = 0; while(low < high) { middle = (low + high)/2; if(target == array[middle]) { return middle; } else if(target < array[middle]) { high = middle; } else if(target > array[middle]) { low = middle + 1; } } return -1; } ~~~ 推荐使用非递归的方式，因为递归每次调用递归时有用堆栈保存函数数据和结果。**能用循环的尽量不用递归。** # 二分查找的应用还是对上一篇博文《[C++如何跳出多层循环](http://blog.csdn.net/luoweifu/article/details/16369007)》中提到的抽签问题进行分析。上一篇博文中是进行了四重循环的嵌套，基时间复杂度是O(n4)，数据大时其计算量会大的惊人。为便于分析，将之前代码帖至如下：

**
抽签问题
解决方案，复杂度n^4 
*/ 
void  drawLots() {
   //从标准输入读入
   int numOfCard, sum;
   int k[MAX_N];
   cout<<"输入numOfCard和sum"<<endl;
   cin>>numOfCard>>sum; 
   cout<<"请输入这sum张卡片的数字"<<endl;
   for(int i=0; i<numOfCard; i++) {
cin>>k[i];
   }
   bool result = false;
   bool isBreakLoop = true;
   int _sum = 0;
   for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
      for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
          for(int c = 0; c < numOfCard && isBreakLoop; c++) {
              for(int d = 0; d < numOfCard && isBreakLoop; d ++) {
              	_sum = k[a] + k[b] + k[c] + k[d];
                  if(_sum == sum) {
result = true;
isBreakLoop = false;
                  }	 
              }
          }
      }
   }
   cout << "_sum:" << _sum << "  " << "sum:" << sum << endl;
   if(result){
   	cout<<"Yes"<<endl;
   } else
    cout<<"No"<<endl;
}

最内层循环所做事如下： Ka + kb + kc + kd = m 移项后如下: Kd = m - (Ka + kb + kc) 到第四层循环时，其实Ka ，kb，kc已经知道，那问题也就变成了对kd的查找，我们可用上面讲的二分查找，复杂度就降为O(n3logn).实现如下： ### 降低复杂度的实现

/**
抽签问题 
解决方案，复杂度n^3 * log(n)
*/ 
void drawLots2() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
    cin>>numOfCard>>sum; 
    cout<<"请输入这sum张卡片的数字"<<endl;
    for(int i=0; i<numOfCard; i++) {
cin>>k[i];
    }
    //对数组进行排序 
    sort(k, k + numOfCard);
int index = -1;
    bool isBreakLoop = true;
    for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
    	for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
        	for(int c = 0; c < numOfCard && isBreakLoop; c++) {
        	index = binarySearch2(k, numOfCard, sum - (k[a] + k[b] + k[c]));
            	if(index >= 0) {
isBreakLoop = false;
                }
          	}
      	}
}
   if(index >= 0){
   	cout<<"Yes"<<endl;
   } else
    cout<<"No"<<endl;
}

### 进一步优化[O(n2logn)] 根据上一步的优化方式，我们可以进一步对内侧两层循环(也就是第三层和第四层)进行思考： Kc+ kd = m - (Ka + kb ) 我们不能直接对Kc+ kd进行查找，但是可以预先枚举出Ka + kb 的n2种数值并排序，再对Kc+ kd进行十分查找。列出枚举O(n2)，排序O(n2logn), 循环O(n2logn)，所以总的复杂度降为O(n2logn)，实现如下：

/**
抽签问题 
解决方案，复杂度n^2 * log(n)
*/ 
void drawLots3() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
    cin>>numOfCard>>sum; 
    cout<<"请输入这sum张卡片的数字"<<endl;
    for(int i=0; i<numOfCard; i++) {
cin>>k[i];
    }
    int cdNum = numOfCard*(numOfCard+1)/2;
    int cdSum[cdNum];
    int i = 0;
    for(int a=0; a<numOfCard; a++) {
    	for(int b=i; b<numOfCard; b++) {
    	cdSum[i ++] = k[a] + k[b];
    	}
    }
    //对数组进行排序 
    sort(cdSum, cdSum + cdNum);
int index = -1;
    bool isBreakLoop = true;
    for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
    	for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
        	for(int c = 0; c < numOfCard && isBreakLoop; c++) {
        	index = binarySearch2(cdSum, cdNum, sum - (k[a] + k[b]));
            	if(index >= 0) {
isBreakLoop = false;
                }
          	}
      	}
}
   if(index >= 0){
   	cout<<"Yes"<<endl;
   } else
    cout<<"No"<<endl;
}

### 进一步思考上面枚举Ka + kb 时其实是有重复的，因为k[i] + k[j] == k[j] + k[i]，去除重复值之后，Ka + kb 值的个数是n(n+1)/2。至于n(n+1)/2怎么来，可以简单推导如下： N M 1 1 2 2+1 3 3+2+1 4 4+ 3+2+1 ...... 实现如下：

/**
抽签问题 
解决方案，复杂度n^2 * log(n)
*/ 
void drawLots3_1() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
    cin>>numOfCard>>sum; 
    cout<<"请输入这sum张卡片的数字"<<endl;
    for(int i=0; i<numOfCard; i++) {
cin>>k[i];
    }
    int cdNum = numOfCard*numOfCard;
    int cdSum[cdNum];
    for(int a=0; a<numOfCard; a++) {
    	for(int b=0; b<numOfCard; b++) {
    	cdSum[a*numOfCard + b] = k[a] + k[b];
    	}
    }
    //对数组进行排序 
    sort(cdSum, cdSum + cdNum);
int index = -1;
    bool isBreakLoop = true;
    for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
    	for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
        	for(int c = 0; c < numOfCard && isBreakLoop; c++) {
        	index = binarySearch2(cdSum, cdNum, sum - (k[a] + k[b]));
            	if(index >= 0) {
isBreakLoop = false;
                }
          	}
      	}
}
   if(index >= 0){
   	cout<<"Yes"<<endl;
   } else
    cout<<"No"<<endl;
}

';

C++如何跳出多层循环

最后更新于：2022-04-01 20:19:40

C++如何跳出多层循环虽然说语言是互通的，各种计算机语言的基本逻辑结构是类似的，但不同的语言之间还是有一些差别的。如循环中的break，在java中可以后面带标志:**break [flag]**(flag为要结束的循环层数)，但在C++中没有这个标志。那C++中如何跳出多重循环呢？ # 以问题为例：

问题主题：抽签

问题描述：

将写有数字的numOfCard个卡片放入口袋中，从口袋中抽取4次卡片，每次记录卡片的数字后将其放回口袋中。设卡片上写的数字为k1、k2、k3...kn,如果这4个数字的和为sum，则输出”Yes”，否则输出”No”

限制条件：

1<=numOfCard<=50

1<=sum<=108

1<=ki<=108

样例1：

输入

numOfCard = 3

Sum = 10

K = {1, 3, 5}

输出

Yes

样例2：

输入

numOfCard = 3

Sum = 9

K = {1, 3, 5}

输出

No

# 可能的解决方法你可能会将程序写成这样：

void drawLots() {

//从标准输入读入

int numOfCard, sum;

int k[MAX_N];

cout<<"输入numOfCard和sum"<<endl;

cin>>numOfCard>>sum;

cout<<"请输入这sum张卡片的数字"<<endl;

for(int i=0; i<numOfCard; i++) {

cin>>k[i];

}

bool result = false;

int _sum = 0;

for(int a = 0; a < numOfCard; a ++) {

for(int b = 0; b < numOfCard; b ++) {

for(int c = 0; c < numOfCard; c++) {

for(int d = 0; d < numOfCard; d ++) {

_sum = k[a] + k[b] + k[c] + k[d];

if(_sum == sum) {

result = true;

break;

}

if(result){

cout<<"Yes"<<endl;

} else

cout<<"No"<<endl;

}

# 出现的问题 **但是上面的break并没有结束循环(即没有跳出多层循环)，而只是跳出了本层循环。**如果你不明白为什么会这样，可以参考我之前写的一篇文章：[再探java基础——break和continue的用法](http://blog.csdn.net/luoweifu/article/details/10756017) 或者，你可以将程序稍微改动一下来验证：

void drawLots() {

//从标准输入读入

int numOfCard, sum;

int k[MAX_N];

cout<<"输入numOfCard和sum"<<endl;

cin>>numOfCard>>sum;

cout<<"请输入这sum张卡片的数字"<<endl;

for(int i=0; i<numOfCard; i++) {

cin>>k[i];

}

bool result = false;

int _sum = 0;

for(int a = 0; a < numOfCard; a ++) {

for(int b = 0; b < numOfCard; b ++) {

for(int c = 0; c < numOfCard; c++) {

for(int d = 0; d < numOfCard; d ++) {

_sum = k[a] + k[b] + k[c] + k[d];

if(_sum == sum) {

result = true;

break;

}

cout << "_sum:" << _sum << " " << "sum:" << sum << endl;

if(result){

cout<<"Yes"<<endl;

} else

cout<<"No"<<endl;

}

输入**样例1**，结果为： _sum:20 sum:10 Yes 原因：_sum:20是因为**break并没有结束循环(即没有跳出多层循环)，而只是跳出了本层循环**，运行到循环最后一次时 k[a] == k[b] == k[c] == k[d] == 5; 那么，如何让程序跳出多重循环呢？ # 我的解题思路是： **1. **java中有break [flat]的用法，可以解决这个问题，试了一下，但发现C++里不行，会报错，可能C++里没有这个用法；**2. **C/C++有个强制跳转的语法goto；**3. **加判断标志，不满足条件时逐层终止 # 我的解决方法： ### 一、使用goto

void drawLots() {

//从标准输入读入

int numOfCard, sum;

int k[MAX_N];

cout<<"输入numOfCard和sum"<<endl;

cin>>numOfCard>>sum;

cout<<"请输入这sum张卡片的数字"<<endl;

for(int i=0; i<numOfCard; i++) {

cin>>k[i];

}

bool result = false;

int _sum = 0;

for(int a = 0; a < numOfCard; a ++) {

for(int b = 0; b < numOfCard; b ++) {

for(int c = 0; c < numOfCard; c++) {

for(int d = 0; d < numOfCard; d ++) {

_sum = k[a] + k[b] + k[c] + k[d];

if(_sum == sum) {

result = true;

goto breakLoop;

}

breakLoop: cout << "_sum:" << _sum << " " << "sum:" << sum << endl;

if(result){

cout<<"Yes"<<endl;

} else

cout<<"No"<<endl;

}

输入样例1. 结果： _sum:10 sum:10 Yes ### 二、加判断标志

void drawLots() {

//从标准输入读入

int numOfCard, sum;

int k[MAX_N];

cout<<"输入numOfCard和sum"<<endl;

cin>>numOfCard>>sum;

cout<<"请输入这sum张卡片的数字"<<endl;

for(int i=0; i<numOfCard; i++) {

cin>>k[i];

}

bool result = false;

bool isBreakLoop = true;

int _sum = 0;

for(int a = 0; a < numOfCard && isBreakLoop; a ++) {

for(int b = 0; b < numOfCard && isBreakLoop; b ++) {

for(int c = 0; c < numOfCard && isBreakLoop; c++) {

for(int d = 0; d < numOfCard && isBreakLoop; d ++) {

_sum = k[a] + k[b] + k[c] + k[d];

if(_sum == sum) {

result = true;

isBreakLoop = false;

}

cout << "_sum:" << _sum << " " << "sum:" << sum << endl;

if(result){

cout<<"Yes"<<endl;

} else

cout<<"No"<<endl;

}

输入样例1. 结果： _sum:10 sum:10 Yes ### 说明：本人还是建议采用方法二，因为方法二更符合结构化的程序设计，使代码更整洁，可读性更强！我还是尽量避免使用goto。欢迎加入"C/C++梦之队" 学习群：226157456

';

蚂蚁爬行问题

最后更新于：2022-04-01 20:19:37

问题主题：Ants(POJ No.1852)

问题描述：

n只蚂蚁以每秒1cm的速度在长为Lcm的竹竿上爬行。当蚂蚁看到竿子的端点时就会落下来。由于竿子太细，两只蚂蚁相遇时，它们不能交错通过，只能各自反方向爬行。对于每只蚂蚁，我们只知道它离竿子最左端的距离为xi，但不知道它当前的朝向。请计算所有蚂蚁落下竿子的最短时间和最长时间。

限制条件：

1<=L<=106

1<=n<=106

0<=xi<=L

样例：

输入

L=10

n=3

x={2,6,7}

输出

min=4{左、右、右}

max=8{右、右、右}

### 【解法一】 ### 解题分析：对于最短时间，我们可以考虑当所有蚂蚁都向最近的端点移动时，这时不会发生两只蚂蚁相碰的情况，也就是时间最短的情况。对于最长时间，你也许会想蚂蚁有向左向右两种情况，相碰之后又向相反的方向移动，n只蚂蚁就有2n种可能,要考虑的情况就会特别多，而随n的增大急剧增加。但你仔细想一下两只蚂蚁相遇时的情况(如下图)会发现，由于相遇时相互反向移动且速度相同，我们可以认为是依原方向移动。如果你是高中生，一定会立马想到物理学中的动能定理…… ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-08-24_57bd6c179761d.jpg) ### 程序实现: **C++**

#include <iostream>

#include <algorithm>

const int L = 10;

const int n = 3;

const int x[n] = {2,6,7};

int main() {

int min, max;

min = max = 0;

int minX, maxX;

for(int i=0; i<n; i++) {

minX = x[i]<L-x[i]?x[i]:L-x[i];

min = minX>=min?minX:min;

maxX = x[i]>(L-x[i])?x[i]:L-x[i];

max= maxX>max ? maxX : max;

}

cout<<min<<" "<<max<<endl;

return 0;

}

**Java****

package programdesign;

public class Ants {

public static void solve(int l, int x[]) {

if(0 >= x.length)

return;

int min , max;

min = max = 0;

int d1, d2;

for(int i=0; i<x.length; i++) {

if(x[i]<=l-x[i]) {

d1 = x[i];

d2 = l-x[i];

} else {

d1 = l-x[i];

d2 = x[i];

}

if(min < d1) {

min = d1;

}

if(max < d2) {

max = d2;

}

System.out.println(min + " " + max);

}

public static void main(String[] args) {

int x[] = {2,6,7};

solve(10, x);

}

**** ### 算法复杂度：时间复杂度O(n)

';

几个比较大的在线提交系统（Online Judge）

最后更新于：2022-04-01 20:19:35

原文：[http://www.cnblogs.com/yqskj/articles/2005038.html](http://www.cnblogs.com/yqskj/articles/2005038.html) 下面是几个比较大的在线提交系统（Online Judge）浙江大学 Online Judge（ZOJ） [http://acm.zju.edu.cn](http://acm.zju.edu.cn/) 国内最早也是最有名气的OJ，有很多高手在上面做题。特点是数据比较刁钻，经常会有你想不到的边界数据，很能考验思维的全面性。北京大学 Online Judge（POJ） [http://acm.pku.edu.cn/JudgeOnline/](http://acm.pku.edu.cn/JudgeOnline/) 建立较晚，但题目加得很快，现在题数和ZOJ不相上下，特点是举行在线比赛比较多，数据比ZOJ上的要弱，有时候同样的题同样的程序，在ZOJ上WA，在POJ上就能AC。同济大学 Online Judge (TOJ) [http://acm.tongji.edu.cn/index.php](http://acm.tongji.edu.cn/index.php) 这个OJ题数上不能与上两个相比，推荐这个OJ的原因是它是中文的，这对很多对英文不太感冒的兄弟是个好消息吧。它也因此吸引了众多高中的OIer，毕竟他们的英文还差一些呵呵，上面的题目也更偏向高中的信息学竞赛一些。西班牙Valladolid大学 Online Judge（UVA） [http://acm.uva.es/](http://acm.uva.es/) 世界上最大最有名的OJ，题目巨多而且巨杂，数据也很刁钻，全世界的顶尖高手都在上面。据说如果你能在UVA上AC一千道题以上，就尽管向IBM、微软什么的发简历吧，绝对不会让你失望的。俄罗斯Ural立大学 Online Judge（URAL） [http://acm.timus.ru/](http://acm.timus.ru/) 也是一个老牌的OJ，题目不多，但题题经典，我在高中的时候就在这上面做题的。　俄罗斯萨拉托夫国立大学(Saratov State University)(SGU) [http://acm.sgu.ru/](http://acm.sgu.ru/) SGU 是俄罗斯萨拉托夫国立大学(Saratov State University)用于培养ACM选手的训练网站。这个网站的建成时期较晚，但随着比赛的举行以及新题目的加入，这个题库的题目也日渐丰富。这个题库的一大特点就是Online Judge功能强大，它不仅使你避开了多数据处理的繁琐操作，还能告诉你程序错在了第几个数据。这一点虽然与ACM的Judge有些出入，但是却方便了调试程序。与UVA相比，这里的题目在时间空间上要求都比较严格，而且更多的考察选手对算法的掌握情况，所以特别推荐冲击NOI的选手也来做一做。 UsacoGate Online Judge（USACO） [http://ace.delos.com/usacogate](http://ace.delos.com/usacogate) 全美计算机奥林匹克竞赛（USACO）的训练网站，特点是做完一关才能继续往下做,与前面的OJ不同的是测试数据可以看到，并且做对后可以看标准解答，所以如果大家刚开始的时候在上面那些OJ上总WA却找不到原因的话，可以试着来这里做做，看看测试数据一般是从什么地方阴你的。

';

从简单的三角形开始

最后更新于：2022-04-01 20:19:33

问题主题：三角形

问题描述：

有n根棍子，棍子i的长度为ai，想要从中选出三根棍子组成周长尽可能长的三角形。请输出最大的周长，若无法组成三角形则输出0。

样例：

输入

n=5

a={2,3,4,5,10}

输出

12(选择3,4,5时)

输入

n=4

a={4,5,10,20}

输出

0(无法构成三角形)

### 【解法一】 ### 解题分析：我的思路(java实现)是： 1.先将棍子根据长度从小到大排序； 2.第一根棍子取最长的a1 = a[n-1]； 3.第二根棍子取次长的a2=a[n-2]； 4.第三根棍子取a3=a[n-3]，如果a1+a2>a3,则说明可以构成三角形，输出最大周长； 5.如不能构成三角形，则a3依次取a[n-4], a[n-5]... 6.如果a3=a[0]时依旧不行，则要循环a2, 使a2依次取a[n-3],a[n-4]... 7.如果再不行，要变换a1值，a1=a[n-2], a2=a[n-3]... 也就是使a1,a2,a3依次从高到低取值。 8.a1,a2,a3分别取到最小值a[2],a[1],a[0]还是不能构成三角形时，输出0，结束计算. 书上的分析(用C++实现)是：直接用三重循环枚举所有的根子选择方案。再用以下公式判断能否构成三角形。最长棍子的长度<其余两个棍子的长度之和 ### 程序实现: **C++**

public void contructTriangle(int a[]) {

// 对数组a进行排序

Arrays.sort(a);

int n = a.length;

int a1, a2, a3;

for (int i = n - 1; i >= 0; i--) {

a1 = a[i];

for (int j = i - 1; j >= 0; j--) {

a2 = a[j];

for (int k = j - 1; k >= 0; k--) {

a3 = a[k];

if (a2 + a3 > a1) {

System.out.println("最大" + (a1 + a2 + a3) + "三角形为" + a1 + "," + a2 + ","

+ a3 );

return ;

}

System.out.println("0, 不能构成三角形");

}

**Java**

#include <iostream>
#include <algorithm>
void constriangle(int* a, int n) {
int ans = 0;	//答案 
int len, ma, result;
//让i<j<k,这样棍子就不会被重复选了
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++) {
for(int k=j+1; k<n; k++) {
len = a[i] + a[j] + a[k];
ma = max(a[i], max(a[j], a[k]));
int rest = len-ma;
if(ma <rest) {
ans = max(ans, len);
}
}
}
}
cout<<ans<<endl;
}
 
int main() {
int a[5] = {2, 3, 4, 5, 10};
constriangle(a, 5);
return 0;
}

**** ### 算法复杂度：时间复杂度：O(n3)

';

前言

最后更新于：2022-04-01 20:19:31

> 原文出处：[算法程序设计](http://blog.csdn.net/column/details/programingdesign.html) 作者：[罗伟富](http://blog.csdn.net/luoweifu) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 算法程序设计 > 本人对数据结构、算法比较感兴趣。从《挑战程序设计（竞赛）》一书中收获颇多！本专栏就是记录我在学习该书时的笔记和所得到的感悟，希望对大家有所帮助，我结合自己的实践分别用C++和Java两种语言进行了实现，两种语言各有各的优点，读者自己去本会吧！

';