精华内容
下载资源
问答
  • 问应如何选择装入背包中物品,使得装入背包中物品价值最大? (要求使用回溯法)   2. (二)算法分析: 01背包属于找最优解问题,用回溯法需要构造解子集树。对于每一个物品i,对于该物品只有选与不选2个...

    题目
    1(一)问题描述:
     给定n种物品和一背包。物品i的重量是wi>0,其价值为vi>0,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? (要求使用回溯法)
     在这里插入图片描述
    2. (二)算法分析:
    01背包属于找最优解问题,用回溯法需要构造解的子集树。对于每一个物品i,对于该物品只有选与不选2个决策,总共有n个物品,可以顺序依次考虑每个物品,这样就形成了一棵解空间树: 基本思想就是遍历这棵树,以枚举所有情况,最后进行判断,如果重量不超过背包容量,且价值最大的话,该方案就是最后的答案。
    在搜索状态空间树时,只要左子节点是可一个可行结点,搜索就进入其左子树。对于右子树时,先计算上界函数,以判断是否将其减去(剪枝)。
    上界函数bound():当前价值cw+剩余容量可容纳的最大价值 <= 当前最优价值bestp。
    为了更好地计算和运用上界函数剪枝,选择先将物品按照其单位重量价值从大到小排序,此后就按照顺序考虑各个物品。

    (三)实验代码:

    #include <iostream>  
    using namespace std;  
    /*
    设计算法解0-1背包问题
    */
    class Knap  
    {
    	friend int Knapsack(int p[],int w[],int c,int n );  
    public:		
    	void print()  
    	{  
    		for(int m=1;m<=n;m++)  
    		{  
    			cout<<bestx[m]<<" ";  
    		}  
    		cout<<endl;  
    	};  
    	
    private:  
    	int Bound(int i);  
    	void Backtrack(int i);  
    	
    	int c;//背包容量  
    	int n; //物品数  
    	int *w;//物品重量数组  
    	int *p;//物品价值数组  
    	int cw;//当前重量  
    	int cp;//当前价值  
    	int bestp;//当前最优值  
    	int *bestx;//当前最优解  
    	int *x;//当前解  
    	
    };  
    
    int Knap::Bound(int i)  
    {  
    	//计算上界  
    	int cleft=c-cw;//剩余容量  
    	int b=cp;  
    	//以物品单位重量价值递减序装入物品  
    	while(i<=n&&w[i]<=cleft)  
    	{  
    		cleft-=w[i];  
    		b+=p[i];  
    		i++;  
    	}  
    	//装满背包  
    	if(i<=n)  
    		b+=p[i]/w[i]*cleft;  
    	return b;  
    }  
    
    void Knap::Backtrack(int i)  
    {  
    	if(i>n)  
    	{  
    		if(bestp<cp)  
    		{  
    			for(int j=1;j<=n;j++)			  
    				bestx[j]=x[j];  
    			bestp=cp;  
    		}  
    		return;  
    	}  
    	if(cw+w[i]<=c) //搜索左子树  
    	{              
    		x[i]=1;  
    		cw+=w[i];  
    		cp+=p[i];  
    		Backtrack(i+1);  
    		cw-=w[i];  
    		cp-=p[i];  
    	}  
    	if(Bound(i+1)>bestp)//搜索右子树  
    	{  
    		x[i]=0;  
    		Backtrack(i+1);  
    	}  
    }  
    
    class Object  
    {  
    	friend int Knapsack(int p[],int w[],int c,int n);  
    public:  
    	int operator<=(Object a)const  
    	{  
            return (d>=a.d);  
    	}  
    private:  
    	int ID;  
    	float d;  
    };  
    
    int Knapsack(int p[],int w[],int c,int n)  
    {  
    	//为 Knap::Backtrack 初始化  
    	int W=0;  
    	int P=0;  
    	int i=1;  
    	Object *Q=new Object[n];  
    	for(i=1;i<=n;i++)  
    	{  
    		Q[i-1].ID=i;  
    		Q[i-1].d=1.0*p[i]/w[i];  
    		P+=p[i];  
    		W+=w[i];  
    	}  
    	if(W<=c)  
    		return P;//装入所有物品  
    	//依物品单位重量排序  
    	float f;  
    	for( i=0;i<n;i++)  
            for(int j=i;j<n;j++)  
            {  
    			if(Q[i].d<Q[j].d)  
    			{  
    				f=Q[i].d;  
    				Q[i].d=Q[j].d;  
    				Q[j].d=f;  
    			}  
    		}  
            
    		Knap  K;  
    		K.p = new int[n+1];  
    		K.w = new int[n+1];  
    		K.x = new int[n+1];  
    		K.bestx = new int[n+1];  
    		K.x[0]=0;  
    		K.bestx[0]=0;  
    		for( i=1;i<=n;i++)  
    		{  
    			K.p[i]=p[Q[i-1].ID];  
    			K.w[i]=w[Q[i-1].ID];  
    		}  
    		K.cp=0;  
    		K.cw=0;  
    		K.c=c;  
    		K.n=n;  
    		K.bestp=0;  
    		//回溯搜索  
    		K.Backtrack(1);  
    		K.print();  
    		delete [] Q;  
    		delete [] K.w;  
    		delete [] K.p;  
    		return K.bestp;  
    }  
    
    void main()  
    {  
    	int *p;  
    	int *w;  
    	   int c=0;  
           int n=0;  
           int i=0;  
    	   
           cout<<"请输入物品个数:"<<endl;   
    	   cin>>n;  
           p=new int[n+1];  
           w=new int[n+1];  
           p[0]=0;  
           w[0]=0;  
    	   
           cout<<"请输入物品的价值:"<<endl;  
           for(i=1;i<=n;i++)
    		   cin>>p[i];  
    	   
           cout<<"请输入物品的重量:"<<endl;  
           for(i=1;i<=n;i++)  
    		   cin>>w[i];  
    	   
           cout<<"请输入背包容量:"<<endl;  
           cin>>c;  
    	   
           cout<<Knapsack(p,w,c,n)<<endl;  
    }
    
    展开全文
  • 我们可以把M看做是一个背包,而给定的数字是价值和重量相等的物品,在容量一定的情况下,我们能选择的最大的价值一定是小于等于背包容量的,也就是<=m,如果最终 f[n][m]==m 说明能选出m的组合,当然也可以用一维...

    题目描述:

    给定N个数字,从N个数字中选择任意k个数字,使之和等于M。

    例如有5个数字:5 3 6 8 4    M=16
    那么可以选择5 3 8使之和为16。

    解题思路:

    我们可以把M看做是一个背包,而给定的数字是价值和重量相等的物品,在容量一定的情况下,我们能选择的最大的价值一定是小于等于背包容量的,也就是<=m,如果最终 f[n][m]==m 说明能选出m的组合,当然也可以用一维01背包,但是如果要求具体组合是哪几个数组成了m,必须通过01背包的二维数组查找。

    代码:

    #include<iostream>
    using namespace std;
    
    int f[100][100];
    int a[100];
    int n,m;
    
    int main(){ 
    	cin>>n>>m;
    	for (int i=1; i<=n; i++)
    		cin>>a[i];
    	for (int i=1; i<=n; i++){
    		for (int j=1; j<=m; j++){
    			if (j>=a[i]) f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
    			else f[i][j]=f[i-1][j];
    		}
    	}
    	for (int i=1; i<=n; i++){
    		for (int j=1; j<=m; j++)
    			cout<<f[i][j]<<" ";
    		cout<<endl;	
    	}
    	if (f[n][m]==m) cout<<"yes"; else cout<<"no";
    }

    姊妹篇:

    从给定的N个正数中选取若干个数之和最接近M【01背包实现】

    展开全文
  •  指导教师要帮助学生作出如下判断:课题所确定的问题有没有研究价值,题目的大小是否合适,所选择的研究途径方法是否可行等。 学生在得到批准后按开题报告的安排来开展论文写作。 2、 开题报告的内容和要求 (1...
  •  指导教师要帮助学生作出如下判断:课题所确定的问题有没有研究价值,题目的大小是否合适,所选择的研究途径方法是否可行等。 学生在得到批准后按开题报告的安排来开展论文写作。 2、开题报告的内容和要求 (1)...
  • 求助:最近,发现了一种新数组排序方法,初测其速度是快速排序法近50倍,想知道有没有市场价值,时间复杂度能计算出来吗?请各位大神赐教! 下面,为了便于区别说明将这个新方法暂且称之占位排序法; 用javascript...
  • 他们强烈的要求自我能力自由,讲求自我意识,拥有坚定的信仰。这些人思维严谨,有逻辑性,做事情效率极高,是一个时候实实在在的智者。要求严苛,性情冷漠,行事比较独立。据说INTJ型人格仅占人口的 2%,女性则...

    64da3d5603009e7202184bdddff03019.png

    在MBTI职业性格类型中,INTJ型人格是天生的 完美主义者,工作中追求卓越,希望能够实现自我价值。他们强烈的要求自我能力和自由,讲求自我意识,拥有坚定的信仰。这些人思维严谨,有逻辑性,做事情效率极高,是一个时候实实在在的智者。要求严苛,性情冷漠,行事比较独立。据说INTJ型人格仅占人口的 2%,女性则更为稀少,只有 0.8%,也常被成为:“建筑师”型人格。

    这种人格的人,内向、直觉、思考、判断,在柯尔塞气质类型测试中是典型的策划者。但凡感兴趣的事物,他们会用强烈的精力去实践。不同于理想主义者的不切实际,这类人格的人既能够瞎想,同时也可以用实际行动去证明。

    下面这两个,是我以前在知乎的回复,貌似点赞还不少,谢谢,这次写mbti系列的稿子,也是源于这个动力。再次向给我点赞的朋友表示感谢。

    MBTI 职业倾向测试在线测试地址有哪些?

    在哪里可以MBTI测试?

    免费 MBTI职业性格测试简洁版 - 在线工具网 - 工作生活好帮手www.zxgj.cn
    bfb20122d07ad4338e03322db0662158.png
    MBTI职业性格测试完整版 - 在线工具网 - 工作生活好帮手www.zxgj.cn
    2ee6cc76ba54423252b0880affc42d1d.png

    1、INTJ型人格的基本特点

    他们具有独特的思想,伟大的梦想,天生精于理论,对于一些复杂的概念往往瞬间就懂。尤其是在战略规划上,会事先对全局形成一个整体性的认识,具有高瞻远瞩的特点。日常生活中思维严谨,足智多谋,与人沟通的时候能够轻而易举说出自己的观点,并且能够用自己的热情去感染对方。

    2、INTJ型人格的专业选择

    喜欢分析,善于总结和判断,能够从整体上把控事物的INTJ型人格,在选择专业的时候可以考虑今后起决定作用的类型。并且,他们对文字和语言的敏感度较高,抽象思维能力强,选择思考性强的专业,也很不错。

    (1)管理学、工商管理、人力资源管理

    (2)艺术学、语言文学、戏剧学

    (3)教育学、哲学、广播电视学

    选择上述专业,完美结合了INTJ型人格的管理能力强、艺术天分高等特点,对那些不知道怎么选择专业的人来说,是一个可信的借鉴。

    专业众多,也无法一一列举,上述仅为参考示例。重视性格分析,抓住这个性格的特征,尤其是优势部分,沿着这个优势来考虑自己的专业,优势就是竞争力

    相关职业测评:霍兰德职业兴趣测试、九型人格测试、大五人格测试 、GATB职业能力倾向测试、艾森克人格测试、disc性格测试、青年人格测验、卡特尔16PF、舒伯职业价值观、自我力量量表。

    3、INTJ型人格的职业选择

    很多职业都适合INTJ型人格的人,他们有勇有谋,并且追求卓越,拥有理想的同时,也愿意埋头苦干,是为数不多的智者型人物。喜欢控制,不喜欢被领导,遇到问题能够据理力争,本性果断,善于谋划,能够广泛听取各方的意见,是拥有极强能力的领导者。

    (1)各大企业经理、人力资源主管、行政主管:出众的领导能力,独特的个人魅力,让INTJ型人格似乎成为一个领导型人格。无论处在哪个岗位,只要将权力赋予他们,便可以得到应有的回报。

    (2)舞蹈演员、作家、话剧表演者、广告策划:艺术天分高、愿意为理想奋斗等特点,在从事文艺表演和创作上极其便利。敏锐的感知能力,能够让他们迅速理解作品的内涵,并且可以通过行动将这份艺术魅力展现出来。

    (3)大学教授、主持人、公务员、哲学家:INTJ型人格善于规划,统筹全局,当他们成为主持人,或者是讲台上的老师,都可以很好地发挥这种特质,将一个场合控制下来。跟他们在一起,很多事情都不需要自己操心,这些人会根据自己的判断,制定一个万无一失的策略。

    ..... 适合的职业不局限于上述参考示例,只要能分析到自己的性格特征 ,重视分析,结合实际,切莫直接搬套,职业和专业都因人而异,没有固定的公式。找到自己的优势擅长,顺势而为,就是获取职业成就的最佳捷径。

    MBTI 专业和职业分析 系列

    Howard:⑨MBTI测试,分析INTP型人格的专业选择和职业选择

    Howard:⑧解读ESTP型人格的专业选择和职业选择@MBTI测试

    Howard:⑦ENFP型人格如何选择专业和职业@MBTI职业性格测试

    Howard:⑥INFJ型人格的专业选择和职业选择,MBTI职业性格测试

    Howard:⑤ISTP型人格@mbti,如何选择专业和职业?

    Howard:④ESTJ型人格(管理型人格)如何选择专业和职业

    Howard:③ENFJ@mbti 解读专业选择和职业选择,MBTI职业性格测试

    Howard:②INFP型人格如何选择专业和职业?@mbti职业性格测试

    Howard:①ISTJ@mbti,如何选专业和职业 - MBTI职业性格测试

    展开全文
  •  第二部分 开题报告 一、开题报告目的 写开题报告目的,是要请老师专家帮我们判断一下:这个问题有没有研究价值、这个研究方法有没有可能奏效、这个论证逻辑有没有明显缺陷。 二、 开题报告结构 就要...
  •  1、毕业论文(设计)题目 毕业论文(设计)题目由学院提供参考题目,学生可根据自己实际情况兴趣选择论文(设计)题目。学生也可根据自己学生、工作中体会或遇到实际问题提出毕业论文(设计)题目,报学院...
  • 因而它是查新员选择数据库、拟订检索词、制定检索策略依据,是进行新颖性结论判断的基矗由此可见,查新点分析、提炼与把握是影响查新质量—个非常重要因素,查新点准确与否直接影响查新结论可靠性针对...
  • 实验原理、实验流程或装置示意图 油脂是膳食中重要组成部分是机体能量主要****之一,油脂氧化酸败会导致风味延展食品成分,如蛋白质其他反应严重变质,变质油脂会减少营养价值且对人体消化器官及...
  • 题面:有n个重量和价值分别为 Wi 与 Vi 物品,现在从这些物品中挑选出总重量不超过 s 物品,并且要求总价值最大。 输入: n=4 S=5 (w,v) = {(2,3)(1,2)(3,4)(2,2)} 输出: 7(选择0,1,3号物品) 对于...

    0-1背包

    重要部分:每次每个物品最多只能选择一次。

    题面:有n个重量和价值分别为 Wi 与 Vi 的物品,现在从这些物品中挑选出总重量不超过 s 的物品,并且要求总价值最大。


    输入:
    n=4
    S=5
    (w,v) = {(2,3)(1,2)(3,4)(2,2)}


    输出:
    7(选择0,1,3号物品)


    对于这个问题我们可以先用最朴素的方法,判断每个物品是否放入背包中。

    	#include<bits/stdc++.h>
    	using namespace std;
    	#define MAX_N 20000        //宏定义
    	//输入
    	int n,s;
    	int w[MAX_N],v[MAX_N];
    	
    	//从第 i 个物品开始挑选总重小于 j 的部分
    	int rec(int i,int j){
    		int res;
    		if(i==n){
    			res=0;
    		}else if(j<w[i]){
    			res=rec(i+1,j);
    		}else{
    			res=max(rec(i+1,j-w[i]+v[i]),rec(i+1,j));
    		}
    		return res;
    	}
    	int main(){
    		scanf("%d%d",&n,&s);
    		for(int i=0;i<n;i++){
    			scanf("%d%d",&w[i],&v[i]);
    		}
    		printf("%d\n",rec(0,s));
    		return 0;
    	}
    

    而使用这个方法的话时间复杂度比较大,当n比较大的时候就会时间超限,所以我们需要优化算法,上面的那个方法对于重复出现的又计算了一遍所以造成时间长,我们可以把每次计算结果都存起来下次再计算到该部分的时候直接拿来使用减少计算时间。

    优化:

    int dp[MAX-N][MAX_N];
    memset(dp,-1,sizeof(dp));//初始化
    
    int rec(int i,int j){
    		if(dp[]i[j]>0){
    			return dp[i][j];
    		}
    		int res;
    		if(i==n){
    			res=0;
    		}else if(j<w[i]){
    			res=rec(i+1,j);
    		}else{
    			res=max(rec(i+1,j-w[i]+v[i]),rec(i+1,j));
    		}
    		return dp[i][j]=res;
    	}
    

    我们上面用的是递归的方法,我们也可以用递推的方法来阶矩这个问题。递推解决这个问题有两个方向,一个是倒序一个是正序。

    倒序:

    int dp[MAX-N][MAX_N];
    void dp_ditui(){ 
    for(int i=n-1;i>=0;i--){ 
    	for(int j=0;j<=S;j++){
    		if(j<w[i]){
    			dp[i][j]=dp[i+1][j];
    		}else{
    			dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);//递推式子不同 
    		}
    	}
    }
    printf("%d\n",dp[0][s]);//输出不同 
    

    正序:

    void dp_ditui(){
    for(int i=0;i<n;i++){ 
    	for(int j=0;j<=S;j++){
    		if(j<w[i]){
    			dp[i+1][j]=dp[i][j];
    		}else{
    			dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
    		}
    	}
    }
    printf("%d\n",dp[n][s]);//输出不同 
    

    以上就是0-1背包的几种常见解决方法,最常用的是后两种。

    //正序与倒序的区别:
    除了方向相反以外还有以下区别:
    //正序
    	printf("%d\n",dp[n][s]);
    //倒序
    	printf("%d\n",dp[0][s]);
    

    完全背包

    重要部分: 每个物品可以选择的次数不止一次,每个物品都可以选择多次。

    题面同上

    #include<stdio.h>
    #include<bits/stdc++.h>
    using namespace std;
    #define MAX_N 10000
    int dp[MAX_N][MAX_N],n,w[MAX_N],v[MAX_N],S;
    void dp_ditui(){
    	for(int i=0;i<n;i++){
    		for(int j=0;j<=S;j++){
    			if(j<w[i]){
    				dp[i+1][j]=dp[i][j];
    			}else{
    				dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);   //注意
    			}
    		}
    	}
    	printf("%d\n",dp[n][S]);
    }
    int main(){
    	scanf("%d%d",&n,&S);
    	for(int i=0;i<n;i++){
    		scanf("%d%d",&w[i],&v[i]);
    	}
    	dp_ditui();
    	return 0;
    }
    

    从上面的代码可以看出完全背包的代码与0-1背包的代码似乎是完全一样的,但是仔细看的话可以发现区别在这里:

    //完全背包
    dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);   //注意
    //0-1背包
    dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
    

    另外无论是0-1背包还是完全背包我们也都可以用一个数组实现。

    0-1背包:

    	int dp[MAX_N];
    	void solve(){
    		for(int i=0;i<n;i++){
    			for(int j=s;j>=w[i];j--){
    				dp[j]=max(dp[j],dp[j-w[i]+v[i]);
    			}
    		}
    		printf("%d\n",dp[s]);
    	}
    

    完全背包:

    int dp[MAX_N];
    	void solve(){
    		for(int i=0;i<n;i++){
    			for(int j=w[i];j<=s];j++){
    				dp[j]=max(dp[j],dp[j-w[i]+v[i]);
    			}
    		}
    		printf("%d\n",dp[s]);
    	}
    

    二者的区别只在与 j 的循环方向:

    0-1背包:
    for(int j=s;j>=w[i];j--)
    完全背包:
    for(int j=w[i];j<=s;j++)
    
    展开全文
  •  定义状态dp[i]表示选择第i个串最大价值  状态转移方程就是 dp[i]=max{dp[j]}+value[i],其中要求0  因此问题就归结于高效判断子串问题,这要求我们把每一个串都保存下来,当然,你记录每个点father也行
  • POJ 1873 /// 状压+凸包

    2019-10-02 15:28:20
    要求最小价值,若存在多种最小价值的方案则选择余下长度更少 树木较少 状态压缩 枚举所有状态 计算当前状态 被选中的价值和长度 其他 被围起来(未被选中)树去求凸包 计算凸包边长(即围栏...
  • 用法:以价值和成本判断消息流量。去除低价值、高成本的流量。抽样调整低价值/低成本价值/高成本以降低成本。 原因:消息流量不是“免费的”,并且对系统提出了昂贵的要求。 要点:不要发布一切消息。对流量...
  • 1500字思想报告范文篇一: 敬爱党组织: 开宗明义,人生价值观是人们关于个人对他人社会作用意义认识、评价和判断,其所阐述是个人对他人社会需要满足以及所能满足程度。而人生价值观解决了三个...
  • 为了更好的满足从容量、性能、可用性、数据安全、数据共享、数据整合等方面的应用,对存储提出的要求,必须采用网络化的存储体系。存储网络化顺应了计算机服务器体系结构网络化的趋势,即目前的内部总线架构将逐渐...
  • 6.22 如何在一个文件中判断声明为extern数组大小(例如,数组定义大小在另一个文件中)?sizeof操作符似乎不行。 6.23 sizeof返回大小是以字节计算,怎样才能判断数组中有多少个元素呢? 第7章 内存分配 ...
  • 二叉排序树与平衡二叉树实现

    热门讨论 2010-12-26 15:25:31
    35% 04 综合运用知识能力 10 能运用所学知识技能去发现与解决实际问题,能正确处理实验数据,能对课题进行理论分析,得出有价值的结论。 05 应用文献能力 5 能独立查阅相关文献从事其他调研;能提出并较...

空空如也

空空如也

1 2 3 4 5
收藏数 81
精华内容 32
关键字:

价值判断和价值选择的要求