蓝桥杯之买商品
公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。 程序输入： 第一行是一个整数m，代表可购买的商品的种类数。 接下来是m个整数，每个1行，分别代表这m种商品的单价。 程序输出： 第一行是一个整数，表示共有多少种方案 第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。 例如： 输入： 2 200 300 则应输出： 2 2 2 5 0 做这道题有三种 第一种
#include <iostream>
using namespace std;
int price[100] = {200,300};
int num[100];
int m = 0;
int count = 0;
int slove(int money)
{
if(money>1000)
{
return 0;
}
if(money==1000)
{
count++;
for(int i = 0; i < m; i++)
{
cout << num[i]<<ends;
}
cout << endl;
// return 0;
}
// 切记不要用这种方法写，会导致重复
for(int i = 0; i < m ; i++)
{
num[i]++;
slove(money+price[i]);
num[i]--;
}
return 0;
}
int main()
{
cin >> m;
slove(0);
}总结：这种方法会将有重复如商品1为0 商品2为0 那么2 2就会有六种二叉树,这种方法使用于有序的排列组合 0011 0101 0110 1100 1010 1001
第二种
#include <stdio.h>
#define N 20
int way[N][N] = {0};
int num[N] = {0};
int price[N]={0};
int count = 0;
int n;
void buy(int money,int i);
void print();
int main()
{
int i;
scanf("%d",&n);
for(i = 0;i<n;i++)
{
scanf("%d",&price[i]);
}
buy(0,0);
print();
return 0;
}
void buy(int money,int i)
{
if(money>1000||i>=n)
return;
if(money==1000)
{
int i;
for(i = 0;i<n;i++)
{
way[count][i] = num[i];
}
count++;
}
num[i]++;
buy(money+price[i],i);
num[i]--;
i++;
num[i]++;
buy(money+price[i],i);
num[i]--;
i--;
}
void print()
{
int i,j;
for(i = 0;i<count;i++)
{
for(j = 0;j<n;j++)
{
printf("%d ",way[i][j]);
}
printf("\n");
}
}总结这种方法在所在的分支上只会往靠向右边子树枝递进 使用于无序排序 如0011 之后不会出现 0101 这里的第三个数的0不会出现只会出现1或2(被排除)
第三种（回溯）
#include <iostream>
#include <cstring>
using namespace std;
int num[100] = {0};
int price[100] ={0};
int count = 0;
int m;
int check()
{
int money = 0;
for(int i = 0;i < m; i++)
{
money += price[i]*num[i];
}
return money;
}
void dfs()
{
int k = 0;
while(k > -1)
{
num[k]++;
while(check()>1000&&num[k]<1000/price[k])
{
num[k]++;
}
if(check()==1000)
{
for(int i = 0;i < m; i++)
{
cout << num[i]<<ends;
}
cout << endl;
}
else if(check()<1000&&k<m)//注意这里是m
{
k++;
}
else
{
num[k] = -1;
k--;
}
}
}
int main()
{
memset(num,-1,100);
cin >> m;
for(int i = 0; i < m; i++)
{
cin >> price[i];
}
dfs();
return 0;
} 总结：回溯法进行剪枝功能，所对应的二叉树与前面的不同
这三道题目的图（画的不太好）
三个程序的图
这道题只实用于第二个和第三个程序
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年01月16日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读