admin 管理员组文章数量: 887021
购物券
题目描述：
公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。
程序输入：第一行是一个整数m，代表可购买的商品的种类数。
接下来是m个整数，每个1行，分别代表这m种商品的单价。
程序输出：
第一行是一个整数，表示共有多少种方案 第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。
例如：
输入： 2 则应输出： 2
200 2 2
300 5 0
输入： 2 则应输出： 1
500 2 0
800
思考：
子集思想
1.以商品的价格种类作为每次向下递归的条件，具体到本题中，将商品的价格种类存到数组a中，就以a的下标作为进入递归的条件，即递归的边界,这样就搞清楚了如何递归的问题;
2.以200， 300情况为例,200最多选5次,300最多选3次，由此来确定循环的边界 money / a[cur]，对total进行i次处理;
3.小技巧：用二维数组保存结果;
正确代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[1010], sum[1010];//sum数组记录每一种的个数
int group[50][50];//用二维数组保存结果；
int money = 1000, num = 0, total = 0;//“减”不可行;
void shopping(int a[], int N, int cur);int main(void)
{int N;while(scanf("%d", &N) != EOF){int i, j, min = 1010;num = 0;memset(group, 0, sizeof(group));for(i = 0; i < N; i++){scanf("%d", &a[i]);}shopping(a, N, 0);printf("%d\n", num);for(i = 0; i < num; i++)//num{for(j = 0; j < N; j++)printf("%d ", group[i][j]);printf("\n");}}return 0;
}
void shopping(int a[], int N, int cur)//cur:数组a的下标, 以下标作为进入递归的层次;
{int i;if(cur == N)//递归边界;{if(total == money){num++;for(i = 0; i < N; i++){group[num - 1][i] = sum[i];//num - 1;}}return;}else{for(i = 0; i <= money / a[cur]; i++)//*****{total = total + a[cur] * i;sum[cur] += i;shopping(a, N, cur + 1);total = total - a[cur] * i;sum[cur] -= i;}}//else
}
错误代码：
用了全排列，里面的for循环使得输出结果有重复的数据：
#include<stdio.h>
#include<stdlib.h>
int a[1010], sum[1010];//sum数组记录每一种的个数
int total = 1000, num = 0;
void shopping(int a[], int N, int total);int main(void)
{int N;while(scanf("%d", &N) != EOF){int i;for(i = 0; i < N; i++)//默认已经排好序;{scanf("%d", &a[i]);}shopping(a, N, total);printf("num = %d\n", num);}return 0;
}
void shopping(int a[], int N, int total)
{int i;if(total <= 0){if(total == 0){num++;for(i = 0; i < N; i++)printf("%d ", sum[i]);printf("\n");}return;}else{for(i = 0; i < N; i++){total -= a[i];sum[i]++;shopping(a, N, total);total += a[i];sum[i]--;}//for}//else
}
本文标签： 购物券
版权声明：本文标题：购物券 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687807616h143875.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论