1.打家劫舍： 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
入：每组测试案例有两行，第一行只有一个整数N，代表着有N间房屋
第二行有N个整数，代表着每间房屋里的金额，金额范围[0, 1000]。
出：你可以得到的最高金额
入： 4 1 3 2 1 5 2 7 9 3 1 出：4 12
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int rob(vector<long>& nums) {
int sumOdd = 0;int sumEven = 0;
for (int i = 0; i < nums.size(); i++) {
if (i % 2 == 0) {
sumEven += nums[i];
sumEven = max(sumOdd, sumEven);
} else {
sumOdd += nums[i];
sumOdd = max(sumOdd, sumEven);
}
}
return max(sumOdd, sumEven);
}
int main() {
long n,sum;
while(scanf("%d",&n)!=EOF) {
vector<long>nums(n); long temp;
for(int i=0; i<n; i++) {
cin>>temp;
nums.push_back(temp);
}
sum=rob(nums);
cout<<sum<<endl;
nums.clear();
}
return 0;
}
2.矩阵链相乘的乘法次数：设 A1, A2, …, An 为矩阵序列，Ai 是阶为 Pi − 1 * Pi 的矩阵 i = 1, 2, …, n。试确定矩阵的乘法顺序，使得计算 A1A2…An 过程中元素相乘的总次数最少.
入：第一行一个整数 n(1≤n≤300) ，表示一共有 n 个矩阵。第二行 n + 1 个整数 P0, P1, …, Pn(1≤Pi≤100) ，第i个矩阵的行数为Pi − 1，列数为Pi.
出：每组数据输出最少的元素乘法次数.
入：5 74 16 58 58 88 80 5 10 1 50 50 20 5 出：342848 3650
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=400; const int MIN=0x3f3f3f3f;
int qq[MAX][MAX]; int n, a[MAX];
int hanshu(int a, int b);
int main() {
while(cin>>n) {
for(int i = 0; i <= n; i ++) {
cin>>a[i];
}
memset(qq, -1, sizeof(qq));
int temp=hanshu(0,n);
cout<<temp<<endl;
}
return 0;
}
int hanshu(int aa, int bb){
if(aa == bb - 1){
return 0;
}
int &ans = qq[aa][bb];
if(ans != -1){
return ans;
}
ans = MIN;
for(int i = aa + 1; i < bb; i ++){
ans=min(ans, hanshu(aa, i) + hanshu(i, bb) + a[aa] * a[i] * a[bb]);
}
return ans;
}
3.投资问题：m 元钱，n项投资，fi(x): 将 x 元投入第 i 个项目的效益。 求使得总效益最大的投资方案。
入：每组数据第一行 m n，表示总共有 m 元和 n 项投资。
接下来 n 行每行 m 个整数 fi(j) 表示第 i 个项目投资 j 元的收益，
对于一切 i，fi(0) = 0。
出：首先输出一行，一个整数表示最大收益。然后第二行依次输出能够得到最大收益的每个项目的投资额，空格隔开。如果有多个解，可输出任意一个。
入：5 4 11 12 13 14 15 0 5 10 15 20 2 10 30 32 40 20 21 22 23 24
出：61 1 0 3 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<cmath>
#include<complex>
#include<vector>
#include<algorithm>
const int maxn = 1e3 + 10; typedef long long LL; int m, n;
LL dp[maxn][maxn];
int inc[maxn][maxn], record[maxn][maxn];
void ReverseOutputAns(int i, int j){
if(i == 0) return;
ReverseOutputAns(i - 1, j - record[i][j]);
printf(" %d" + (i == 1), record[i][j]);
}
int main(){
while(scanf("%d%d", &m, &n) != EOF){
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i ++){
inc[i][0] = 0;
for(int j = 1; j <= m; j ++)
scanf("%d", &inc[i][j]);
}
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= m; j ++){
dp[i][j] = record[i][j] = 0;
for(int k = 0; k <= j; k ++){
if(inc[i][k] + dp[i - 1][j - k] > dp[i][j]){
dp[i][j] = inc[i][k] + dp[i - 1][j - k];
record[i][j] = k;
}
}
}
}
printf("%d\n", dp[n][m]);
ReverseOutputAns(n, m);
printf("\n");
}
return 0;
}
4.最长公共子序列：求两个序列的最每组测试样例都为一行，两组字符串，每组不超过1000，用空格隔开。求最长公共子序列，都为小写字母。
入：每组测试样例都为一行，两组字符串，每组不超过1000，用空格隔开。
出：对于每个测试实例，输出最长公共子序列的长度，每个实例的输出占一行。
入：abcfbc abfcab programming contest abcd mnp 出：4 2 0
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> >vec;set<string>k;
int sum; string x,y;
int checklength(int a, int b);
void out(int a,int b, string list);
int main() {
while(cin>>x>>y) {
int x1=x.length(); int x2=y.length();
sum=checklength(x1, x2);
cout<<sum<< endl;
}
return 0;
}
int checklength(int a, int b) {
vec=vector<vector<int> >(a+1,vector<int>(b+1));
for(int i=0; i<a+1; ++i) {
for(int j=0; j<b+1; ++j) {
if (i == 0 || j == 0) {
vec[i][j] = 0;
} else if(x[i-1] == y[j-1]) {
vec[i][j] =vec[i-1][j-1] + 1;
} else {
vec[i][j] = max(vec[i-1][j], vec[i][j-1]);
}
}
}
return vec[a][b];
}
void out(int a, int b, string list) {
while (a>0 && b>0) {
if (x[a-1] == y[b-1]) {
list.push_back(x[a-1]);
--a;--b;
} else {
if (vec[a-1][b] > vec[a][b-1]) {
--a;
} else if (vec[a-1][b] < vec[a][b-1]) {
--b;
} else {
out(a-1, b,list);out(a, b-1,list);
return;
}
}
}
reverse(list.begin(),list.end());
k.insert(list);
}
5.最大子串和：给定一个整数数组，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
入：有多组测试数据。 对于每组测试数据，第一行只有一个整数N，代表着数组的大小。第二行有N个整数
出：每组测试数据仅输出一行，包括一个整数，表示最大子串和。
入：9 -2 1 -3 4 -1 2 1 -5 4 出：6
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
class problem {
public:
int submax(vector<int>& nums) {
int len = nums.size();
vector<int> a(len);
a[0] = nums[0];
int ans = a[0];
for(int i = 1; i < len; i++) {
a[i] = max(a[i-1] + nums[i],nums[i]);
ans = max(ans,a[i]);
}
return ans;
}
};
int main() {
int n,temp,sum;
problem pro;
while(cin>>n) {
vector<int>nums(n);
for(int i=0; i<n; i++) {
cin>>temp;
nums.push_back(temp);
}
sum=pro.submax(nums);
cout<<sum<<endl;
nums.clear();
}
return 0;
}
6.最长递增子序列：给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）例如: 1 3 2 5 4 7 6 9 8, 最长递增子序列为1 3 5 7 9
入：输入数据首先包括一个整数 T(1≤10),表示测试实例的个数。
每个测试实例的第一行是一个整数 N(2≤N≤5000) ，表示序列的长度。
第二行数字是一组数组，且所有的整数均在区间 [0,106]内。
出：输出最长递增子序列的长度，每个实例的输出占一行。
入：1 9 1 3 2 5 4 7 6 9 8 出：5
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
class problem {
public:
int checklength(vector<int>& nums) {
int com=0;
if (nums.size() <= 1) {
return nums.size();
}
vector<int> list(nums.size()+1, 1);
for(int i = 1; i < nums.size(); i++) {
for(int j = 0; j < i; j++) {
if(nums[i] > nums[j]) {
list[i] = max(list[j] + 1, list[i]);
}
}
if (list[i] > com) {
com = list[i];
}
}
return com;
}
};
int main() {
int t; int n, temp;
cin >> t; problem pro;
for (int i = 0; i < t; i++) {
cin>>n;
vector<int>nums(n);
for(int i=0;i<n;i++){
cin >> temp;
nums.push_back(temp);
}
int sum = pro.checklength(nums);
cout << sum-1 << endl;
nums.clear();
}
return 0;
}
7.01饭卡：如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。 某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
入：多组数据。对于每组数据： 第一行为正整数n，表示菜的数量。n<=1000。 第二行包括n个正整数，表示每种菜的价格。价格不超过50。 第三行包括一个正整数m，表示卡上的余额。m<=1000。n=0表示数据结束。
出：对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。文章来源：https://www.toymoban.com/news/detail-820696.html
入：1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0 出：-45 32文章来源地址https://www.toymoban.com/news/detail-820696.html
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main() {
int n,sum;int a[2000];int b[2000];
while (scanf("%d",&n)!=EOF) {
if(n==0){//不做输出要求
break;
}
memset(b, 0, sizeof(b));
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
sort(b + 1, b + 1 + n);
int com_sum = b[n];
cin >> sum;
memset(a, 0, sizeof(a));//初始化0
if (sum < 5) {//输入前
cout << sum<<endl;
continue;
}
sum = sum - 5;
for (int i = 1; i <= n-1 ; i++) {
for (int j = sum; j >= b[i]; j--) {
int op=a[j - b[i]] + b[i];
a[j] = max(a[j], op);
}
}
int temp=sum + 5 - a[sum] - com_sum;
cout << temp <<endl;
}
}
到了这里，关于算法设计与分析 实验三 动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
