本文主要是介绍2011年蓝桥杯第九题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这道题目的意思也很简单,核心就是枚举,对于m种商品,每种商品个数有0到 i 种可能,value*i<=now,其中value为商品的单价,now为总钱数1000 - 已经消费的钱数,也就是目前剩余的总钱数,用深搜枚举所有可能,下面是代码:
#include <stdio.h>
#include <stdlib.h>
#define Max 1000 //数据上限,最多有1000种商品
int value[Max]; //记录每种商品的价格
int record[Max]; //记录每种商品的个数
int dif[Max][Max];//记录可能的所有商品个数组合
int ans=0;//记录所有可能成立情况个数
int n;
void Dfs(int now,int pivot){ //now为当前还剩余的钱数,pivot为当前商品下标if(pivot==n){ if(now==0){for(int i=0;i<n;i++)dif[ans][i]=record[i];ans++;}return ;}int temp=now,i=0;while(i*value[pivot]<=now){//从商品数为0开始不断增加试探,枚举所有可能的取值record[pivot]=i;temp-=i*value[pivot];Dfs(temp,pivot+1);i++;temp=now;}
}
int main(){scanf("%d",&n);int i,j;for(i=0;i<n;i++)scanf("%d",&value[i]);Dfs(1000,0); //最开始还剩1000,没有花费任何钱,从商品标号为0开始printf("%d\n",ans);for(i=0;i<ans;i++){for(j=0;j<n;j++)printf("%d ",dif[i][j]);printf("\n");}return 0;
}
注意当没有可能情况的时候输出应该为0
这篇关于2011年蓝桥杯第九题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!