追猫的熊

用户名：20191121

访问量：4621

签　名：

等　　级
排　　名	7331
经　　验	1324
参赛次数	1
文章发表	8
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

每一个不曾起舞的日子，都是对生命的辜负

TA的其他文章

蓝桥杯算法提高VIP-数的划分-题解(C++代码)
浏览：158

蓝桥杯算法提高VIP-聪明的美食家-题解(C++代码)
浏览：167

蓝桥杯算法提高VIP-贪吃的大嘴-题解(C++代码)
浏览：402

你可能喜欢

蓝桥杯算法提高VIP-促销购物-题解(C++代码)

　　作者: 追猫的熊　　　　发表时间：2020-01-17 19:20:45 浏览：733　|　评论：2　

原题链接：蓝桥杯算法提高VIP-促销购物

这个代码写的十分丑陋......见笑了。思路也不是很好。暴力搜索法超时11%我也没有办法啊啊啊啊啊啊啊啊。
```cpp
#include<iostream>
#define min(a,b) (a<b)?(a):(b)
using namespace std;
int n_way;
int way[105][1000]={0};//浪费空间，但实现比较容易
int cost[105]={0};//每种方法的钱数 
int list[1000]={0};//需要买的东西 
int n_type;// 商品种类 
int tag[5]={0};//商品标号 
int price[6][6][6][6][6];
bool judge(int a,int b,int c,int d,int e,int f);//确保没有瞎推(瞎推不会影响结果，看形式运算量甚至可能更小......)
int main(void)
{
	int n,x,y;
	cin>>n_way;
	for(int i=0;i<n_way;i++){
		cin>>n;
		while(n--){
		cin>>x>>y;
		way[i][x]=y;
		}
		cin>>cost[i];
	}
	cin>>n_type;//仅仅是储存在这而已，懒得另建数组 
	for(int i=0;i<n_type;i++){
	cin>>x>>y;
	way[i+n_way][x]=1;
	cin>>cost[i+n_way];
	tag[i]=x;
	list[tag[i]]=y;
	}
	for(int i=0;i<=list[tag[0]];i++)
	for(int j=0;j<=list[tag[1]];j++)
	for(int k=0;k<=list[tag[2]];k++)
	for(int m=0;m<=list[tag[3]];m++)
	for(int n=0;n<=list[tag[4]];n++){
		price[i][j][k][m][n]=25000;//初始化
	}
	price[0][0][0][0][0]=0;
	for(int i=0;i<=list[tag[0]];i++)
	for(int j=0;j<=list[tag[1]];j++)
	for(int k=0;k<=list[tag[2]];k++)
	for(int m=0;m<=list[tag[3]];m++)
	for(int n=0;n<=list[tag[4]];n++){
	for(int o=0;o<n_way;o++){//既然一起买一定更划算，可以先把不必单买的情况的花费求出 
	if(judge(i,j,k,m,n,o)){//这个o命名的比较失败，易与0混淆 
price[i][j][k][m][n]=min(price[i][j][k][m][n]
,price[i-way[o][tag[0]]][j-way[o][tag[1]]][k-way[o][tag[2]]][m-way[o][tag[3]]][n-way[o][tag[4]]]+cost[o]);//令人绝望 
	}
	}
	}
	for(int i=0;i<=list[tag[0]];i++)
	for(int j=0;j<=list[tag[1]];j++)
	for(int k=0;k<=list[tag[2]];k++)
	for(int m=0;m<=list[tag[3]];m++)
	for(int n=0;n<=list[tag[4]];n++){
	if(price[i][j][k][m][n]==25000) continue;
	int temp=price[i][j][k][m][n];
	temp+=cost[n_way]*(list[tag[0]]-i);
	temp+=cost[n_way+1]*(list[tag[1]]-j);
	temp+=cost[n_way+2]*(list[tag[2]]-k);
	temp+=cost[n_way+3]*(list[tag[3]]-m);
	temp+=cost[n_way+4]*(list[tag[4]]-n);
price[list[tag[0]]][list[tag[1]]][list[tag[2]]][list[tag[3]]][list[tag[4]]]=min(temp
,price[list[tag[0]]][list[tag[1]]][list[tag[2]]][list[tag[3]]][list[tag[4]]]);
	}
	cout<<price[list[tag[0]]][list[tag[1]]][list[tag[2]]][list[tag[3]]][list[tag[4]]]<<endl;
	return 0;
}
bool judge(int a,int b,int c,int d,int e,int f)
{
		if(a<way[f][tag[0]]) return 0;
		if(b<way[f][tag[1]]) return 0;
		if(c<way[f][tag[2]]) return 0;
		if(d<way[f][tag[3]]) return 0;
		if(e<way[f][tag[4]]) return 0;
		if(price[a-way[f][tag[0]]][b-way[f][tag[1]]][c-way[f][tag[2]]][d-way[f][tag[3]]][e-way[f][tag[4]]]==25000) return 0;
		return 1;
}
```
这个是超时的朴素暴力搜索。思路倒还常规？还望大佬指教，如何才能不超时呢
```cpp
#include<iostream>
using namespace std;
int mincost=25000;
int n_way;
int way[105][1000]={0};//浪费空间，但实现比较容易
int cost[105]={0};//每种方法的钱数 
int list[1000]={0};//需要买的东西 
int b;// 商品种类 
int tag[5]={0};//商品标号 
bool pos(int i);//第i种way是否可行. 
bool over(void);//是否买完 
void buy(int money);
int main(void)
{
	int n,x,y;
	cin>>n_way;
	for(int i=0;i<n_way;i++){
		cin>>n;
		while(n--){
		cin>>x>>y;
		way[i][x]=y;
		}
		cin>>cost[i];
	}
	cin>>b;//仅仅是储存在这而已，懒得另建数组 
	for(int i=0;i<b;i++){
	cin>>x>>y;
	way[i+n_way][x]=1;
	cin>>cost[i+n_way];
	tag[i]=x;
	list[tag[i]]=y;
	}
	buy(0);
	cout<<mincost<<endl;
	return 0;
}
bool pos(int i)
{
	for(int j=0;j<b;j++){
		if(list[tag[j]]<way[i][tag[j]])
		return false;
	}
	return true;
}
bool over(void)
{
	for(int i=0;i<b;i++){
		if(list[tag[i]]!=0) return false;
	}
	return true;
}
void buy(int money)
{
	if(money>mincost) return ;
	if(over()){
		mincost=money;
		return ;
	}
	bool flag=0;
	for(int i=0;i<n_way;i++){
		if(!pos(i)) continue;
		flag=1;
		for(int j=0;j<b;j++) list[tag[j]]-=way[i][tag[j]];
		buy(money+cost[i]);
		for(int j=0;j<b;j++) list[tag[j]]+=way[i][tag[j]];
	}
	if(!flag){
		for(int i=0;i<b;i++){
			money+=list[tag[i]]*cost[i+n_way];//反正马上就结束了,money改动没什么 
		}
		mincost=(mincost<money)?mincost:money;
	}
}
```

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

ALonPursuit

tips：说错了，动态规划可以有很高的效率

2020-08-23 13:48:16

ALonPursuit

tips：可以适当剪枝、加快输入流

2020-08-23 13:42:51

追猫的熊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯算法提高VIP-促销购物-题解(C++代码)

评论区

精彩推荐

众数问题（C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-数字母（C语言代码）

WU-输出九九乘法表（C++代码）

演讲大赛评分（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

小O的乘积（C语言代码）

字符删除（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

追猫的熊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯算法提高VIP-促销购物-题解(C++代码)

评论区

精彩推荐

众数问题 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-数字母 （C语言代码）

WU-输出九九乘法表 （C++代码）

演讲大赛评分 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

小O的乘积 （C语言代码）

字符删除 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

　　评论区

众数问题（C++代码）

C语言训练-数字母（C语言代码）

WU-输出九九乘法表（C++代码）

演讲大赛评分（C语言代码）

小O的乘积（C语言代码）

字符删除（C语言代码）