少年Q

用户名：yin19990129

访问量：25365

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

[STL训练]2010辽宁省决赛 SPY （C++代码）只做最好的思路！
浏览：339

[STL训练]{A} + {B}-题解(C++代码)只做最好的思路！
浏览：415

[STL训练]第36届ACM亚洲区大连站网络赛The kth great number-题解(C++代码)只做最好的思路！
浏览：300

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

31.简化型背包-题解(C++代码)只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-04-01 23:19:18 浏览：402　|　评论：0　

原题链接：简化型背包

这题有点坑，但从表面看来力求最大值，好像可以用贪心，于是就入坑了，错误67%，o(╥﹏╥)o。。。代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;

struct object{
	int p;
	int v;
	int w;
}M[5];
bool cmp(object a,object b){
	return a.p>b.p;
}
int main(){
    int V,W;
	cin>>V>>W;
	for(int i=0;i<5;i++){
		cin>>M[i].p>>M[i].v>>M[i].w;
	}	
	sort(M,M+5,cmp);
	int sum,vs,ws;
	sum=0,vs=0,ws=0;
	for(int i=0;i<5;i++){
		if(vs<V&&ws<W){
		   sum+=M[i].p;
		   vs+=M[i].v;
		   ws+=M[i].w;
		}
	}
	cout<<sum<<endl;
	return 0;
}
```
找不到错误原因，后来听了老师傅的讲解后，恍然大悟！贪心往往得不到最优解，枚举是慢了点，但只要不限制时间，总会得到正确解。这句话在这题体现的淋漓尽致。。。
一般枚举都是采用for循环嵌套，但繁琐麻烦，老师傅给了我们一个新的思路，就是用递归来枚举，对于这题，老师傅给了一个经典的代码。（递归枚举）代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,W,V,ans;
int p[105],w[105],v[105];
bool ce[105];

void fun(){
	int wi,vi,tmp;
	wi=0,vi=0,tmp=0;
	for(int i=1;i<=n;i++){
		wi+=w[i]*ce[i];
		vi+=v[i]*ce[i];
		tmp+=p[i]*ce[i];
	}
	if(wi<=W&&vi<=V&&tmp>ans){
		ans=tmp;
	}
}
void getans(int num){
	if(num>n){
		fun();
		return ;
	}
	for(int i=0;i<=1;i++){
		ce[num]=i;
		getans(num+1);
		ce[num]=0;
	}
}
int main(){
	cin>>n>>W>>V;
	for(int i=1;i<=n;i++){
		cin>>p[i]>>v[i]>>w[i];
	}
	getans(1);
	cout<<ans<<endl;
	return 0;
}
```
这段代码写的简直完美，老师傅的功底深藏不露。
自己在码递归枚举时，一定要注意一个细节，也是递归的条件，就是：
if(num>n){
		fun();
		return ;
	}
这里return;一定要有！！！不然递归不成立。
老师傅无论是这里采用bool变量还是整体代码的逻辑切合都是恰到好处，堪称经典的模板，大家多看看，以后可以套用这个模板思路。

0.0分

2 人评分

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

少年Q

TA的其他文章

你可能喜欢

台球碰撞（C++代码）

【计算球体积】（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

点我有惊喜！你懂得！

C语言训练-排序问题<1> （C语言代码）

31.简化型背包-题解(C++代码)只做最好的思路！

评论区

精彩推荐

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

计算质因子（C++代码）

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

【蟠桃记】（C语言代码）

Hello, world! （C语言代码）

剪刀石头布（C++代码）

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

小O的数字（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

汽水瓶（C语言代码）

少年Q

TA的其他文章

你可能喜欢

台球碰撞 （C++代码）

【计算球体积】 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

点我有惊喜！你懂得！

C语言训练-排序问题<1> （C语言代码）

31.简化型背包-题解(C++代码)只做最好的思路！

评论区

精彩推荐

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

计算质因子 （C++代码）

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

【蟠桃记】 （C语言代码）

Hello, world! （C语言代码）

剪刀石头布 （C++代码）

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

小O的数字 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

汽水瓶 （C语言代码）

台球碰撞（C++代码）

【计算球体积】（C语言代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

计算质因子（C++代码）

【蟠桃记】（C语言代码）

剪刀石头布（C++代码）

小O的数字（C语言代码）

汽水瓶（C语言代码）