软件工程算法课程习题（二）"/>
LDU软件工程算法课程习题（二）
问题 A: 0-1背包问题（基于暴力）
题目描述
给定一个容积为m的背包，去尝试装n个重量为wi、价值为vi的物体，求能装下的物体的最大价值。
输入
输入的第一行有两个整数n和m，分别表示物品的个数，背包的最大容量。
接下来n行，每行两个数字，每个物品的重量w和价值v
数据保证1<=n<=20，1<=w , v<=2000
输出
一个整数，表示可获得的最大价值。
样例输入
3 30
16 45
15 25
15 25
样例输出
50思路：典型的01背包问题，每一个物品只有取和不取，枚举价值判断是否需要取
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10;
int v[maxn],w[maxn];
int dp[maxn*100];
int main()
{int n,back;scanf("%d%d",&n,&back);for(int i = 0;i < n;i++)scanf("%d%d",w+i,v+i);dp[0] = 0;for(int i = 0;i < n;i++){for(int j = back;j >= w[i];j--){dp[j] = max(dp[j],dp[j-w[i]]+v[i]);} }printf("%d\n",dp[back]);return 0;
}问题 B: 八皇后问题（基于暴力）
题目描述
皇后问题。所谓的n皇后问题，是指在n×n的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
为了使问题更加有趣，我们需要求在n×n的棋盘上，放置k个皇后，共有多少种可能的方案数？
输入
两个正整数n和k，（n,k<=10）
输出
一个整数，表示方案数。
样例输入
8 8
样例输出
92思路：这是一个n*n棋盘的k皇后问题，相比于n皇后问题我们可以不放皇后，所以dfs的过程中从0开始放表示不放。
#include<bits/stdc++.h>
using namespace std;
int cow[15];
int ans = 0;
int curzero;
int flag;
int n,k;
bool isgood(int x)
{if(cow[x] == 0 && curzero == n-k)return false;if(cow[x] == 0)return true;for(int i = 1;i < x;i++){if(cow[i] != 0){if(abs(i-x) == abs(cow[i]-cow[x]) || cow[i] == cow[x])return false;}}return true;
}
void dfs(int t)
{if(flag == k){ans++;return ;} if(t > n)return;for(int i = 0;i <= n;i++){cow[t] = i; if(isgood(t)){//cout<<i<<" "<<flag<<" "<<t<<endl;if(i == 0)curzero++;elseflag++;dfs(t+1);if(i == 0)curzero--;elseflag--;}}
}
int main()
{scanf("%d%d",&n,&k);if(n == 0 || k == 0){printf("0\n");return 0;}curzero = 0;flag = 0;dfs(1);printf("%d\n",ans);}问题 C: 李白饮酒--蓝桥杯原题改编（基于暴力）
题目描述
话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数。
为了使问题更加有趣，我们假设他遇到店s次，花f次，你的任务是计算此时的方案总数。
输入
两个整数s和f，分别表示李白遇到的店和花的次数。（s+f<=20）
输出
一个整数，表示方案总数。
样例输入
5 10
样例输出
14
思路：李白饮酒暴力每一种情况然后检查
#include<bits/stdc++.h>
using namespace std;int main()
{int s,f;scanf("%d%d",&s,&f);int two[25] = {0,1,0,1,1,0,0,1,0,0,1,0,0,0,0};int temp = (1 << (s+f));int start,flower,drink,cnt;int ans = 0;for(int i = 0;i <= temp;i++){start = 0,flower = 0,drink = 2,cnt = s+f;memset(two,0,sizeof(two));int number = i;while(number){two[cnt--] = number%2;number/=2;}for(int j = 1;j <=(s+f);j++){if(two[j] == 1){start++;drink *= 2;}if(two[j] == 0){flower++;drink -= 1;}}if(start == s && flower == f && drink == 0 && two[s+f]!=1)ans++;}printf("%d\n",ans);return 0;
}
问题 D: 组素数
题目描述
素数就是不能再进行等分的数。比如：2、3、5、7、11 等。9 = 3 * 3 说明它可以3等分，因而不是素数。
我们国家在1949年建国。如果只给你 1、9、4和9 这4个数字卡片，可以随意摆放它们的先后顺序，那么，你能组成多少个4位的素数呢？
比如：1949，4919 都符合要求。
为了使问题更加有趣，我们输入n个数字，求这n个数字可以组成的数字中的素数。
输入
第一行一个整数n。(n<=6)
第二行n个空格分隔的整数，仅包含1~9
输出
输出所有符合的素数。若没有可行解，则输出-1。
样例输入
4
1 9 4 9
样例输出
1949
4919
9419
9491
9941
思路：全排列然后判断是否是素数
#include <stdio.h>
#include<math.h>
#define M 999999
int a[M]={0};
int n;
int count=0;void perm(int start,int num[]){int i, temp;int flag=1;int sum=0;if(start== n-1){ count++;int i;for(i = 0; i < n; ++i){sum+=num[i]*pow(10,n-1-i);}a[sum]++;for(int j=2;j<sqrt(sum);j++){if(sum%j==0){flag=0;break;}}if(a[sum]==1&&flag)printf("%d \n",sum);else{count--;return ;}}int temp1;for(i = start;i <n;i++){temp1=num[start];num[start]=num[i];num[i]=temp1;perm(start + 1,num);temp1=num[start];num[start]=num[i];num[i]=temp1;}return;
}int main(){scanf("%d",&n);int num[n];for(int i = 0; i < n; i++){scanf("%d",&num[i]);}int temp;for(int k=0;k<n;k++){for(int i=0;i<n-k-1;i++){if(num[i]>num[i+1]){temp=num[i];num[i]=num[i+1];num[i+1]=temp;}}}perm(0,num);if(count==0){printf("-1");}return 0;
}
问题 E: 匪警110问题
题目描述
匪警请拨110,即使手机欠费也可拨通！为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！
某批警察叔叔正在进行智力训练：
12 3 4 5 6 7 8 9 = 110
请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。
请你利用计算机的优势，帮助警察叔叔快速找到所有答案。形如：
12+34+56+7-8+9
123+4+5+67-89
....
为了使问题更加有趣，我们把后面的数字110换成n。注意：这里只要求你计算方案数。不必输出每种方案。
输入
一个整数n，如题所述。(-2000000000<=n<=2000000000)
输出
一个整数，表示方案数。
样例输入
110
样例输出
10
思路：三进制枚举每一种情况然后判断
#include<bits/stdc++.h>
using namespace std;
int number[10] = {1,2,3,4,5,6,7,8,9};
int pp[10];
int qow(int x,int y)
{int res = 1;while(y){if(y&1)res *= x;x *= x;y/=2;}return res;}
int main()
{int n;scanf("%d",&n);int ans = 0;int temp = qow(3,8);for(int i = 0;i < temp;i++){memset(pp,0,sizeof(pp));int res = 0;int now = i;int l = 0,pre;int cnt = 0;for(int j = 0;j < 8;j++){pp[cnt++] = now%3;now /= 3;}int j =0;l = number[0];while(pp[j] == 0 && j < 8){l = l*10+number[j+1];j++;}res += l;pre = pp[j];l = number[j+1];for(int k = j+1;k < 8;k++){while(pp[k] == 0 && k < 8){l = l*10+number[k+1];k++;}if(pre == 1){res += l;pre = pp[k];l = number[k+1];}else{res -= l;pre = pp[k];l = number[k+1];}}if(pre == 1)res += l;if(pre == 2)res -= l;if(res == n)ans++; }printf("%d\n",ans);return 0;
}
问题 F: 敢死队
题目描述
G将军有一支训练有素的军队，这个军队除了G将军外，每名士兵都有一个直接上级（可能是其他士兵，也可能是G将军）。现在G将军将接受一个特别的任务，需要派遣一部分士兵（至少一个）组成一个敢死队，为了增加敢死队队员的独立性，要求如果一名士兵在敢死队中，他的直接上级不能在敢死队中。请问，G将军有多少种派出敢死队的方法。注意，G将军也可以作为一个士兵进入敢死队。
输入
输入的第一行包含一个整数n（1<=n<=20），表示包括G将军在内的军队的人数。军队的士兵从1至n编号，G将军编号为1。接下来n-1个数，分别表示编号为2, 3, ..., n的士兵的直接上级编号，编号i的士兵的直接上级的编号小于i。
输出
一个整数，表示方法数
样例输入
4
1 2 3
样例输出
7思路：稍有难度，树形dp，从最后面开始，因为第i个士兵的上司一定是i之前的一个人，所以从后面开始，如果此人去 那么就要乘上后面的人不去也就是下级的情况，如果此人不去那么要乘上下级去或者不去即两种情况加起来的情况
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int dp[1050][2];
vector <int> person[1050];
int main()
{int n,x;scanf("%d",&n);for(int i = 2;i <= n;i++){scanf("%d",&x);person[x].push_back(i);}int cur;for(int i = n;i >= 1;i--){dp[i][0] = 1,dp[i][1] = 1;cur = person[i].size();for(int j = 0;j < cur;j++){dp[i][0] = dp[i][0]%mod*(dp[person[i][j]][0]+dp[person[i][j]][1])%mod;dp[i][1] = dp[i][1]%mod*dp[person[i][j]][0]%mod;}}int ans = (dp[1][0]+dp[1][1]-1+mod)%mod;printf("%d\n",ans);return 0;
}
问题 G: 独立任务最优调度问题
题目描述
用两台处理机A和B处理n个作业。设第i个作业交给A处理需要时间ai，交给B处理需要时间bi。由于各作业的特点和机器的性能关系，ai和bi之间没有明确的大小关系。既不有将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个算法，使得这两台机器处理完这n个作业的时间最短。
输入
第一行一个整数n，表示任务数（1<=n<=20）。
第二行n个整数，分别表示第i个任务在机器A上的处理时间。
第三行n个整数，分别表示第i个任务在机器B上的处理时间。
处理时间数据范围（1~40）
输出
一个整数，表示最少的完成这些任务的时间 。
样例输入
3
1 4 7
2 5 8
样例输出
7思路：二进制枚举每一种情况然后找最小的就可以了
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10;
int work_A[maxn],work_B[maxn];
int main()
{int n;scanf("%d",&n);for(int i = 0;i < n;i++)scanf("%d",&work_A[i]);for(int i = 0;i < n;i++)scanf("%d",&work_B[i]);int temp = (1 << n);int ans = 10000000;int sumA,sumB;for(int i = 0;i <= temp;i++){sumA = 0;sumB = 0;int number = i;for(int j = 0;j < n;j++){if(number & 1)sumA += work_A[j];elsesumB += work_B[j];number /= 2;}//cout<<sumA<<" "<<sumB<<endl;ans = min(ans,max(sumA,sumB));}printf("%d\n",ans);return 0;
}
更多推荐
LDU软件工程算法课程习题（二）
发布评论