精华内容
下载资源
问答
  • 背包问题贪心算法求解

    万次阅读 多人点赞 2019-10-06 22:14:11
    题目 有一个背包背包容量是M=150。有7个物品,物品可以分割成任意大小。...这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而0-1背包问题却不能用贪心算法求解。 求解步骤 用...

    题目

    有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
    要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
    在这里插入图片描述

    思路

    具有最优子结构性质和贪心选择性质。只要是所有物品的总重量大于背包容纳量,那么背包一定能装满。注意背包问题与0-1背包问题的区别。
    这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而0-1背包问题却不能用贪心算法求解。

    求解步骤

    用贪心算法解背包问题的基本步骤:首先计算每种物品单位重量的价值v[i]/w[i],然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。

    代码实现

    #include <iostream>
    using namespace std;
    //按照单位重量的价值量大小降序排列
    void Sort(int n,float *w,float *v)
    {
        int i,j;
        float temp1,temp2;
        for(i=1;i<=n;i++)
        for(j=1;j<=n-i;j++)//冒泡排序
        {
            temp1=v[j]/w[j];
            temp2=v[j+1]/w[j+1];
            if(temp1<temp2)
            {
                swap(w[j],w[j+1]);
                swap(v[j],v[j+1]);
            }
        }
    }
    int main()
    {
        float w[101];//用来表示每个物品的重量
        float v[101];//用来表示每个物品的价值量
        float x[101];//表示最后放入背包的比例
        int n;//物品数
        float M;//背包最大容纳重量
        cin>>n>>M;
        //依次输入每件物品的重量和价值量
        for(int i=1;i<=n;i++)
            cin>>w[i]>>v[i];
        //按照单位重量的价值量大小降序排列
        Sort(n,w,v);
        int i;
        for(i=1;i<=n;i++)
            x[i]=0;//初始值,未装入背包,x[i]=0
        float c=M;//更新背包容纳量
        for(i=1;i<=n;i++)
        {
            if(c<w[i])  break;//不能完全装下
            x[i]=1;
            c=c-w[i];
        }
        if(i<=n)
            x[i]=c/w[i];
        //输出
        for(int i=1;i<=n;i++)
            cout<<"重量为"<<w[i]<<"价值量为"<<v[i]<<"的物品"<<"放入的比例为"<<x[i]<<endl;
        return 0;
    }
    
    

    在这里插入图片描述

    算的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此,算法的计算时间上界为O(nlogn)。
    为了证明算法的正确性,还必须证明背包问题具有贪心选择性质。

    对于0-1背包问题,贪心选择之所以不能得到最优解是因为在这种情况下,它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。事实上,在考虑0-1背包问题时,应比较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。
    实际上也是如此,动态规划算法的确可以有效地解0-1背包问题。

    展开全文
  • 背包问题贪心算法实现,简单易懂,初学者可参考
  • 物品课分割的装载问题称为背包问题,物品不可分割的装载问题称为0-1背包问题。 #include #include using namespace std; //按性价比贪心策略 typedef struct three { double w; //重量 double v; //价值 double p...
  • 01背包问题贪心算法,详细解析,令你很快懂的01背包问题中的贪心算法思想
  • 0-1背包问题贪心算法

    2015-06-07 12:51:15
    算法课程的0-1背包问题贪心算法代码,含截图,经测试可用
  • 01背包贪心算法前言合并区间最后一块石头的重量 前言 昨天在做力扣探索的时候遇到了两道数组题,看到题目的时候就感觉不知道如何下手。 苦思冥想一番,最后去偷看了答案,发现是贪心算法01背包。 因为之前听说...

    前言

    昨天在做力扣探索的时候遇到了两道数组题,看到题目的时候就感觉不知道如何下手。
    苦思冥想一番,最后去偷看了答案,发现是贪心算法和01背包。
    因为之前听说面试中很少出贪心和背包问题的题目,所以本来打算直接跳过,但是后来一看代码,不长,那还是了解一下吧。

    合并区间

    题目地址:合并区间
    题目大意:给出一个区间的集合,合并所有区间。

    这道题我一开始想了很久,想用单调栈来实现,当一个数进入的时候,弹出所有小于等于这个数的栈元素。
    但是遇到了一个问题,当栈中元素为[1,4]的时候,我再放入[1,4]会导致栈直接为空。
    想了一会没有想到什么好的解决方案,于是就去偷瞄了一眼答案,发现我一开始就走歪了,合并区间是一道经典的贪心算法的题目。

    解题思路:
    对于这道题来说,我们应该首先将数组按左区间升序排序,如果左区间一样就按右区间降序排序。
    这样我们遇到两个区间左区间相同的时候就可以直接跳过。
    对于相邻的两个区间,假设这两个区间为int[] preint[] cur,如果pre的右区间大于cur的左区间也就是说pre[1] <= cur[0],那么说明这两个区间是可以合并的。
    合并之后的右区间由谁决定呢?
    显然是两个区间中右区间比较大的那个。

    所以我们不难得出如下代码:

    class Solution {
        public int[][] merge(int[][] intervals) {
            if(intervals == null || intervals.length == 0 || intervals[0].length == 0)
                return new int[0][0];
            int[][] res = new int[intervals.length][2];
            int index = 0;
            Arrays.sort(intervals,(v1,v2)->((v1[0]==v2[0]) ?v2[1]-v1[1]:v1[0]-v2[0]));
            for(int[] tmp:intervals){
                if(index != 0 && tmp[0] == res[index-1][0])
                    continue;
                if(index == 0 || tmp[0] > res[index-1][1]){
                    res[index++] = tmp;
                }else{
                    res[index-1][1] = Math.max(tmp[1],res[index-1][1]);
                }
            }
            return Arrays.copyOf(res,index);
        }
    }
    

    最后一块石头的重量

    题目地址:最后一块石头的重量

    解题思路:
    对于01背包问题,通常的做法是给出一个二维数组int[][] dp
    dp[i][[j]代表的是当背包容量剩下j,选择是否拿第i个物品(这边是第i个物品,实际中是item[i-1],因为一般我们不说第0个物品,所以不要搞错了)之后背包最大的价值。
    对于任意状态dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])

    那么这道问题和01背包有什么关系呢?
    要使得最后一块石头的重量最小,我们可以把石头分成两堆,使得两堆的差最小。
    也就是在背包上限为(总重量)/2的时候尽可能的取石头使得石头总重量最重(价值最高)。
    那么我们不难得出如下代码:

    class Solution {
        public int lastStoneWeightII(int[] stones) {
            int sum = 0;
            for(int i=0;i<stones.length;i++)	
                sum += stones[i];
            int length = stones.length+1;
            int width = sum/2;
            //这边要注意,数组dp[i][j]指的是第i-1个物品,所以不要写错了
            int dp[][] = new int[length][width+1];
            for(int i=1;i<length;i++){
                for(int j=1;j<=width;j++){
                        if( j >= stones[i-1])
                            dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                        else
                            dp[i][j] = dp[i-1][j];
                    }
                }
            return sum - 2*dp[length-1][width];
        }
    }
    

    一般对于01背包问题,我们最后可以用滚动数组来代替二维数组,但是要注意,当更新j的时候是从后向前更新的,这是因为后面的状态依赖二维数组下左边格子和上面格子的状态,代码如下:

        public int lastStoneWeightII(int[] stones) {
            int sum = 0;
            for(int i=0;i<stones.length;i++)	
                sum += stones[i];
            int length = stones.length+1;
            int width = sum/2;
            int dp[]= new int[width+1];
            for(int i=1;i<length;i++){
            	//注意这边,从后向前更新
                for(int j=width;j>=0;j--){
                        if( j >= stones[i-1])
                            dp[j] = Math.max(dp[j],dp[j-stones[i-1]]+stones[i-1]);
                        else
                            dp[j] = dp[j];
                    }
                }
            return sum - 2*dp[width];
        }
    
    展开全文
  • 运用贪心策略解决0 1背包问题 void beibao(int *w,int *v,int *x,int n,int *C) { int i,j,temp; for(i=0;i;i++) for(j=i+1;j;j++) if(v[i]/w[i][j]/w[j]) { temp=v[i]; v[i]=v[j]; v[j]=temp...
  • 背包问题 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 现在有很多物品(它们是可以分割的),我们知道它们每个物品的单位重量的价值v和重量w(1<=v,w<=10);如果给...

                                                                                               背包问题 
    时间限制:3000 ms | 内存限制:65535 KB 
    难度:3 
    描述 
    现在有很多物品(它们是可以分割的),我们知道它们每个物品的单位重量的价值v和重量w(1<=v,w<=10);如果给你一个背包它能容纳的重量为m(10<=m<=20),你所要做的就是把物品装到背包里,使背包里的物品的价值总和最大。 
    输入 
    第一行输入一个正整数n(1<=n<=5),表示有n组测试数据; 
    随后有n测试数据,每组测试数据的第一行有两个正整数s,m(1<=s<=10);s表示有s个物品。接下来的s行每行有两个正整数v,w。 
    输出 
    输出每组测试数据中背包内的物品的价值和,每次输出占一行。 
    样例输入 

    3 15 
    5 10 
    2 8 
    3 9 
    样例输出 
    65

    注意这个背包问题中,给出的是单位重量的价值,而且物品是可以分割的。

    qsort用法:

     

    /*
      思路:使用贪心算法。为了使背包里的物品总价值最大,先装单位价值最大的,依次类推,
            整放物品,不能整放分割放  
    
      1.定义一个结构体,变量名bao[10],里面定义 单位价值和每个物品重量 
      2.对物品的单位 价值从大到小排序。 
      3.输入信息,并计算出每一个物品的总价值。 
      4.整放物品,计算出满足条件的物品的总价值,总质量。 
      5.分割,背包所容纳的最大质量减去目前的质量乘以分割物品的价值,计算总价值。跳出循环 
    */
     
    //注意:不要忘记每次循环都要初始化数组 
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    struct pack{
    	int v;
    	int w;
    	int total;
    }bao[10];
    
    int cmp(const void *a,const void *b){
    	return(*(pack*)b).v-(*(pack*)a).v;
    } 
    
    int main(){
    	int n,s,i,j;
    	int vsum,wsum,m;
    	scanf("%d",&n);
    	while(n--){
    		memset(bao,0,sizeof(bao));   //排序 
    		scanf("%d%d",&s,&m);
    		for(i=0;i<s;i++){
    			scanf("%d%d",&bao[i].v,&bao[i].w);
    			bao[i].total = bao[i].w*bao[i].v;
    		}//计算每个物品总价值
    		qsort(bao,10,sizeof(bao[0]),cmp);
    		
    		wsum = 0; vsum = 0;
    		for(i=0;i<s;i++){
    			if(m>=(wsum+bao[i].w)){    //整放物品 
    				vsum+=bao[i].total;
    				wsum+=bao[i].w;
    			}
    			else if(m<(wsum+bao[i].w)&&m>=wsum){   //不能整放 ,就分割放 
    				vsum+=(m-wsum)*bao[i].v;
    				break;
    			}
    		} 
    		printf("%d\n",vsum);
    	}
    	return 0;
    }

     

     

     

     

     

    展开全文
  • 背包问题 贪心算法

    2009-05-11 18:10:07
    给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1≤i≤...
  • 贪心算法解决背包问题,用netbeans做的。百分百下载就可以直接运行。JAVA 源文件。
  • 01背包学习贪心算法和动态规划

    千次阅读 2015-05-01 21:31:36
    01背包学习贪心算法和动态规划: 算法的思路其实很大程度上都是相通的,比如在提升算法运行时间的不断探索中,我们用分治的思想来将一个大问题分解为很多小问题进行求解,并且这些子问题与原问题的结构是一样的,...

    从01背包学习贪心算法和动态规划:
    算法的思路其实很大程度上都是相通的,比如在提升算法运行时间的不断探索中,我们用分治的思想来将一个大问题分解为很多小问题进行求解,并且这些子问题与原问题的结构是一样的,比如归并排序,比如第i层是排四个数,第i+1层则是排八个数,问题的规模发生变化但结构不变。而动态规划则是沿用的分治的思想,但是比分治多两个必要条件:重叠子问题和最优子结构。前者要求问题空间要足够小,得到的递归算法会反复求解相同的子问题,而不是产生新的子问题,比如LCS和01背包;而后者则比较晦涩,具体来说就是如果要找问题的最优解先确定该问题最优解包含了其子问题最优解,这样就把责任一层层推下去(在程序中体现在直到遇见哨兵为止)。二贪心算法则又是延续动态规划,因为动态规划自底向上计算总是要维护一个二维数组记录所有的子问题解,对于有些优化问题,没有必要都计算。这时候我们可以使用自上而下的策略,做出一个选择,然后求剩下的子问题,如果面临两个选择,则选择一个,继续求解该子问题即可。
    那么接下来我们用01背包问题具体说明这两种算法:
    问题描述:
    有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
    https://img-blog.csdn.net/20150501212932504

    package DP;
    
    import java.awt.*;
    import java.util.Scanner;
    
    public class bagdp {
        static final int NIF = 9999;
        static int N;//背包数目
        static int[] worth;//单个物品价值
        static int[] cap;//单个物品容量
        static int[][] values;//存放价值,也是自上而下求解问题的必备数据结构
        static int maxVal;//最大价值
        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
            maxVal = in.nextInt();
            N = in.nextInt();
            worth = new int[N+1];
            cap = new int[N+1];
            values = new int[N+1][maxVal+1];
            for(int i = 1;i <= N;i++){
                worth[i] = in.nextInt();
                cap[i] = in.nextInt();
            }
            for(int i = 0;i <= N;i++)
                for(int j = 0;j <= maxVal;j++)
                    values[i][j] = NIF;
            for(int i = 0;i <= N;i++)
                values[i][0] = 0;
            for(int i = 0;i <= maxVal;i++)
                values[0][i] = 0;
            //System.out.print("可装最大价值为:"+greedy(N,maxVal)+"\n");
            System.out.print("可装最大价值为:"+greedy2()+"\n");
            printBags();
    
            in.close();
        }
        public static int greedy(int i,int j){//贪心算法
            if(values[i][j] < NIF) return values[i][j];//备忘录
            if(j < cap[i]) values[i][j] = greedy(i-1,j);//容不下就不要了
            if(j >= cap[i]){//可以容得下
                values[i][j] = max(greedy(i-1,j),greedy(i-1,j-cap[i])+worth[i]);
            }
            return values[i][j];
        }
    
        public static int greedy2(){//动态规划算法,自下而上
            for(int i = 1;i <= N;i++)
                for(int j = 1;j <= maxVal;j++)
                {
                    if(j < cap[i]) values[i][j] = values[i-1][j];
                    else if(j >= cap[i]){
                        values[i][j] = max(values[i-1][j],values[i-1][j-cap[i]]+worth[i]);
                    }
                }
            return values[N][maxVal];
        }
    
        public static int max(int a,int b){
            return a>b?a:b;
        }
    
        public static void printBags(){//回溯打印选择的背包
            int j = maxVal;
            for(int i = N;i > 0;i--){
                if(values[i][j] > values[i-1][j]){
                    System.out.print("背包"+i+"  ");
                    j = j -cap[i];
                    if(j < 0) break;
                }
            }
        }
    }
    greedy是贪心算法(采用了备忘录自上而下的思想),greedy2则采用动态规划思想。
    展开全文
  • 贪心算法贪心算法贪心算法贪心算 背包问题背包问题背包问题
  • 算法,背包问题贪心算法 讲述背包问题。对于学习这一部分的学习者,可以起作用。
  • C#基于贪心算法下的01背包问题 C#基于贪心算法下的01背包问题 C#基于贪心算法下的01背包问题
  • c语言-背包问题贪心算法

    千次阅读 2020-12-03 15:15:14
    //表示该号物品放在多少背包里 int order[MAX];//表示物品的序号,相当其名字 }Solution; Solution X; int m=15;//背包容量 int n=7;//物品数量 int p[]={10,5,15,7,6,18,3}; int w[]={2,3,5,7,1,4,1}; void ...
  • 蓝桥杯 背包问题 贪心算法 Java

    千次阅读 2018-03-17 11:00:17
    http://blog.csdn.net/icydate/article/details/79589590问题描述:设有n个物体和一个背包,物体i的重量为wi ,价值为vi ,背包的容量为C.若将物体i的xi部分(1≤i≤n, 0≤xi≤1)装入背包,则具有价值为vi xi. 目标是找到...
  • 背包问题贪心算法

    2012-06-14 10:38:45
    背包问题中,取得最优解一直是解决背包问题的最终目的,就贪心算法的动态规划关系以及方案在解决背包问题上作比较,但贪心法在什么时候都能取到最优解并无一般结论,而对于普通背包问题我们却有一个完美的结果——贪心...
  • 贪心算法 背包问题

    2012-03-18 16:17:05
    贪心算法 背包问题
  • 这是一个应用贪心算法解决背包问题的完整的程序,供大家参考!
  • 普通背包_贪心算法

    2013-12-18 10:07:50
    普通背包_贪心算法,VC++全程编写,易懂易用
  • 贪心算法编写的01背包问题 用c语言编写 附上实验结果及代码
  • 一、问题描述 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 二、算法策略 单位价值化 三、核心代码 static double ...
  • 贪心算法Q3——01背包问题 /* 问题描述: 有n件物品,每个物品都有一个大小和价值,给你一个固定容量的背包,要求装的东西价值总和最大 实例: 现在有重量分别为35 30 60 50 40 10 25,价值分别为10 40 30 50 35 ...
  • 贪心算法01背包算法实验报告1.问题2.解析3.设计4.分析5.源码 实验报告 课程名称 《算法分析与设计》 实验名称 贪心算法01背包算法 1.问题 [描述算法问题,首选形式化方式(数学语言),其次才是非形式化方式...
  • 0-1背包问题,部分背包问题。分别实现0-1背包的DP算法,部分背包贪心算法和DP算法。附件中包含所有算法源代码.c文件,修改下文件名直接编译执行即可
  • 背包问题贪心算法背包问题 ---- * 已知有n种物品和一个可容纳M重量的背包,每种物品i的重量是w[i]。假定将物品i的一部分x[i]放入背包就会得到p[i]x[i]的效益,这里, * 0[i],p[i]>0.采用怎样的方法才能使装包...
  • 贪心算法-背包装载问题
  • 2019独角兽企业重金招聘Python工程师标准>>> ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,505
精华内容 5,402
关键字:

01背包问题贪心算法