每日一练

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;
}

解决方法：

解决方法：

解决方法：

解决方法：

解决方法：

原文地址：https://www.cnblogs.com/ZarkY/p/17284041.html