1..笑笑买贺卡（贪心算法）
题目：新年快到了,笑笑打算给他的好朋友们发贺年卡,而且它已经选好了自己要购买的贺卡的样式.俗话说得好,货比三家,笑笑来到了商店,看了各个商铺这种贺卡的价钱.不仅如此,笑笑还记住了每个商铺的存货量.已知笑笑打算购买m 张贺卡,问他最少花多少钱.
输入格式：
第一行有两个整数m 和n .其中m 表示要购买贺年卡的数量,n 表示商铺的个数.
以下n 行,每行有两个整数,分别表示该商铺这种贺年卡的单价和存货量.
输出格式：
仅一个数,表示笑笑所花的最少钱数.
输入样例：
要买 行
10 4
单价 存货量
4 3
6 2
8 10
3 6
输出样例：
36
数据规模：
0 ＜ m ,n ≤ 1000
可以保证最后的结果在长整型范围内,商铺的总存货量不少于m .
测试数据：
10 4
4 3
6 2
8 10
3 6
输出结果：
36
解决方法：
#include <stdio.h>
struct shop{
int price;
int store;
};
int main(){
int m,n,i,j;
scanf("%d %d",&m,&n);
struct shop s[n];
for(i=0;i<n;i++){
scanf("%d %d",&s[i].price,&s[i].store);
}
//求笑笑所花的最少钱数.
//排序，根据单价排序
int min;
struct shop temp;
for(i=0;i<n-1;i++){
min=i;
for(j=i;j<n;j++){
if(s[j].price<s[min].price){
min=j;
}
}
temp=s[min];
s[min]=s[i];
s[i]=temp;
}
int money=0;
i=0;
while(m>0){
if(m>=s[i].store){
money=money+s[i].store*s[i].price;
m=m-s[i].store;
}else if(m<s[i].store){
money=money+m*s[i].price;
m=m-m;
}
i++;
}
printf("%d\n",money);
}
2.0-1背包问题（动态规划）
已知n种物品和一个可容纳C重量的背包，物品i的重量为wi,产生的效益为pi,在装包时物品i可以装入，也可以不装，但不可以拆开装。即物品i可产生的效益为pi,这里xi为0或1。请问如何装包，能使装包总效率最大。
Input
多组测试数据。 每组第一行输入2个整数，分别为C和物品种数n 然后是n行，每行输入2个整数，分别是物品的重量wi和物品产生的效益pi
Output
对于每组数据输出1行，包含2个数分别为装包的重量及产生的效益
Sample Input
60 6
15 32
17 37
20 46
12 26
9 21
14 30
Sample Output
60 134
解决方法：
#include <stdio.h>
#include <math.h>
struct bag{
int weight;
int price;
};
int main(){
int n,c,i,j;
scanf("%d %d",&c,&n);
struct bag bg[n+1];
for(i=1;i<=n;i++){
scanf("%d %d",&bg[i].weight,&bg[i].price);
}
int dp[n+1][c+1];
//初始
for(i=0;i<=c;i++){
dp[0][i]=0;
}
for(i=0;i<=n;i++){
dp[i][0]=0;
}
//写入
for(i=1;i<=n;i++){
for(j=1;j<=c;j++){
if(bg[i].weight<=j){//比较
dp[i][j]=fmax(dp[i-1][j],dp[i-1][j-bg[i].weight]+bg[i].price);
}else{//抄上一格
dp[i][j]=dp[i-1][j];
}
}
}
printf("%d\n",dp[n][c]);
//输出商品 从最后一个往前
j=c;
for(i=n;i>0;i--){
if(dp[i][j]>dp[i-1][j]){
printf("%d ",i);
j=j-bg[i].weight;
}
if(j<=0)
break;
}
}
3.素数分解
验证 1000 以内的正偶数都能够分解为两个素数之和。请写出程序输出分解结果。
#include <stdio.h>
int isPrime(int n);
int main(){
int i,j;
for(i=4;i<=2000;i+=2){
for(j=2;j<=i;j++){
if(isPrime(j)==0&&isPrime(i-j)==0){
printf("%d+%d=%d\n",j,i-j,i);
break;
}
}
}
return 0;
}
//判断是不是质数
int isPrime(int n){
if(n==1||n==0)
return 1;//不为质数
int i;
for(i=2;i<n;i++){
if(n%i==0){
return 1;
}
}
return 0;
}
解决方法：
解决方法：
解决方法：
解决方法：
解决方法：