算法学习笔记

01背包问题

题目描述：

给定几件物品和一个容量为为c的背包，第i件物品的重量为wi， 价值为是 vi，每件物品只能使用1次，求解将哪些物品装入背包后物品价值的总和最

输入

输入第一行为两个整数n，c，分别表示物品数量和背包的容量，其后有n行，每行包含两个整数w, v，分别表示该物体的重量和其产生的价值。

输出

输出最大的价值总和

样例输入

5 10
2 6
2 3
6 5
5 4
4 6

样例输出

15

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int n,c;
	cin>>n>>c;//物品数量，背包容量 
	vector<int>w(n+1),v(n+1);//重量和价值 
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	vector<vector<int> >dp(n+1,vector<int>(c+1,0));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=c;j++) 
		{
			if(j<w[i])//物品的重量大于当前背包容量 
			{
				dp[i][j]=dp[i-1][j];
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//能放下当前物品：
				//放当前物品，不放当前物品 
			 } 
		}
	}
	cout<<dp[n][c]<<endl;
}

跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

输入

多组测试样例。每组测试样例包含一个整数n。(1<=n<=100)

输出

每组测试样例输出一行，表示青蛙跳上n级台阶的跳法数量.

所得到的结果模1000000007

样例输入

3
4

样例输出

3
5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//简化long long 
int main()
{
	ll n;
	while(cin>>n)
	{
		ll *a=new ll [n+1];//开辟一个一维数组（从0开始n个数所以为n+1） 
		a[0]=1;
		a[1]=1;
		for(int i=2;i<=n;i++)
		{
			a[i]=a[i-1]%1000000007+a[i-2]%1000000007;//最后一步跳了一个台阶或者二个台阶 
		}
		cout<<a[n]%1000000007<<endl;
	}
	return 0;
}

最长公共子序列

题目描述

一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad" ,顺次选1，3，5个字符就构成子串" cad" ,现给定两个字符串，求它们的最长共公子串。

输入

第一行两个字符串用空格分开。两个串的长度均小于2000 。

输出

最长子串的长度。

样例输入

abccd aecd

样例输出

3

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	string str1,str2;
	cin>>str1>>str2;
	int len1=str1.size();
	int len2=str2.size();
	vector<vector<int> > dp(len1+1,vector<int>(len2+1));
	for(int i=1;i<=len1;i++)
	{
		for(int j=1;j<=len2;j++)
		{
			if(str1[i-1]==str2[j-1])
			{
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		 } 
	}
	cout<<dp[len1][len2];
	return 0;
}

三角形的路径权

题目描述

如输入样例所示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1< 三角形行数< 25；三角形中的数字为整数< 1000；


输入

输入第一行为N，表示有N行 后面N行表示三角形每条路的路径权。

输出

输出路径所经过的数字的总和最大的答案。
 

样例输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出

30

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int ans=0;
int main()
{
	int n;
	cin>>n;
	vector<vector <int> >data(n+1,vector<int>(n+1,0));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>data[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			data[i][j]+=max(data[i-1][j],data[i-1][j-1]);
			if(data[i][j]>ans)
			{
				ans=data[i][j];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

题目描述：
问题描述：给定一个由n行数字组成的数字三角形，如图3-7所示。试设计一个算法，计算出从三角形的定制顶至底的一条路径，使该路径经过的数字总和最大。
算法设计：对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
输入
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0...99之间。
输出
输出数据只有一个整数，表示计算出的最大值.
样例输入
5

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30