65
2011 藍橋杯【初賽試題】 程序設計題二
公司發了某商店的購物券1000元，限定隻能購買店中的m種商品。每種商品的價格分別為m1,m2,…，要求程序列出所有的正好能消費完該購物券的不同購物方法。
程序輸入：
第一行是一個整數m，代表可購買的商品的種類數。
接下來是m個整數，每個1行，分別代表這m種商品的單價。
程序輸出：
第一行是一個整數，表示共有多少種方案
第二行開始，每種方案占1行，表示對每種商品購買的數量，中間用空格分隔。
例如：
輸入：
2
200
300
則應輸出：
2
2 2
5 0
輸入：
2
500
800
則應輸出：
1
2 0
#include<stdio.h>
#include<string.h>
int cost;
int n;//物品個數
int price[2000];//物品單價
int num[100];//物品數目
int sum=0;//方案數目
int arg[100][100];//每種方案的商品分布
void Fun(int x)//遞歸,每件物品分為買或者不買的情況（同一物品可以買多次）
{
int i;
if(cost>1000||x>=n)
return;
if(cost==1000)
{
for(i=0; i<n; i++)
arg[sum][i] = num[i];
sum++;
return;
}
num[x]++;//選擇這件商品的情況
cost+=price[x];
Fun(x);//還可能繼續選這件商品
num[x]--;//不選擇這件商品的情況
cost-=price[x];
Fun(x+1);//往下走
}
int main()
{
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&price[i]);
memset(num,0,sizeof(num));//數組清0為了之後的加減運算
Fun(0);
printf("%d\n",sum);
for(i=0;i<sum;i++)
{
printf("%d",arg[i][0]);//防止多輸出空格
for(j=1;j<n;j++)
printf(" %d",arg[i][j]);
puts("");
}
return 0;
}
參考：https://www.cnblogs.com/hxsyl/archive/2012/12/15/2819911.html
最後更新：2017-04-03 12:55:32