ACM基础:贪心之背包问题knapsack_sandalphon4869的博客-程序员宅基地_贪心背包问题

技术标签: # ACM基础  


一、背包问题

1.描述

小偷抢劫商店,发现n件物品,物品i价值 v i v_i vi美元,重量为 w i w_i wi磅,小偷在背包中最多只能携带W磅重量,但他想尽可能多地携带贵重物品。他应该带哪些物品?

问题符号:

  • n:物品的个数
  • i:物品的序号
  • v i v_i vi:某物品的价值value
  • w i w_i wi:某物品的重量weight
  • W:背包的最大承重量

解法符号:

  • x i x_i xi:表示该物品装入背包多少。在0-1背包问题中,0(不拿)或1(拿走整件);在分数背包问题中,是个浮点数 [ 0.0 , 1.0 ] [0.0, 1.0] [0.0,1.0]0.0(不拿)或0.x(拿走部分)或1.0(拿走整件)

解法:
在满足 ∑ 1 ≤ i ≤ n w i ∗ x i ≤ W \displaystyle \sum_{1\leq i\leq n}w_i*x_i\leq W 1inwixiW的条件下,使 ∑ 1 ≤ i ≤ n v i ∗ x i \displaystyle \sum_{1\leq i\leq n}v_i*x_i 1invixi最大。

2.难度划分

依据 x i x_i xi是分数还是01,命名:

  • 简单:分数背包问题(Fractional knapsack)
  • 难:0-1背包问题(0-1 knapsack)

二、简单:分数背包问题(Fractional knapsack)

1.思路

因为可以拿走物品的部分,所以不妨将所有物品打碎当成单位物品来看,我们只需要拿走性价比(价值vi/重量wi)最高的单位物品就行,依照性价比降序来拼凑重量够整个背包。

在这里插入图片描述

2.伪代码

// v是vi数组,每个物品的价值
// w是wi数组,每个物品的重量
// W是背包的最大负重
// x是xi数组,每个物品装入背包的多少
// n是物品的数量
// 注意:对v数组和w数组有要求,按照性价比降序排列物品,即v(i)/w(i) ≥ v(i+1)/w(i+1)
GREADY-KNAPSACK(v, w, W, x, n)
	// 初始化都为0,哪个都不装入
	x ← 0
	// 背包的剩余容量,开始什么都不装
	c ← W
	// 遍历每个物品
	for i ← 1 to n
			// 如果物品的重量小于等于背包剩余容量,则可装入
		do	if w(i) ≤ c
					// 装入整件物品
			then	x(i)1
					// 背包剩余容量变少
					c ← c - w(i)
			// 如果装不进去,那么退出for循环
			else	exit
	
	// i ≤ n表示exit退出for循环(注意:for成功遍历完每个物品后,i++的最后结果是i=n+1)
	// 如果i ≤ n,说明两种情况,一种是整件物品装不进去但可以装进部分,另一种是背包剩余空间用尽了
	if i ≤ n
			// 装入该物品的部分:剩余空间/物品总重
			// 第二种情况进入没事,因为c = 0 时,x(i) = 0
			// 不存在c>=w(i)的情况,要不然就不会exit退出for循环
	then	x(i) ← c/w(i)
	return x

3.c++实现

#include <iostream>
#include <string.h>
using namespace std;

// 物品的个数
#define n 5

// 调整为性价比降序
void costPerformance_insertSort(double v[n], double w[n])
{
    
    // int c[n] = {};
    // for(int i = 1;i<n;i++)
    // 遍历第二个到最后一个,为A[i],表示要插入排序好部分的元素。
    // 因为第一个不用比较,所以从第二个开始
    for (int i = 1; i < n; i++)
    {
    
        // 当前待插入的元素
        double key_v = v[i];
        double key_w = w[i];
        // 将A[i]插入到已经排序好的部分,就是A[i]前面的部分A[1...i-1]
        // 倒着看前面的,确定要插入的位置
        int j = i - 1;
        // 在不越界时,并且因为是降序所以是当前一个元素更小时继续
        while (j >= 0 && v[j] / w[j] < key_v / key_w)
        {
    
            // 前一个元素后移
            v[j + 1] = v[j];
            w[j + 1] = w[j];
            // 再往前面一个
            j--;
        }
        // 此时才正式插入元素
        // 因为退出while循环时是A[j]>=key,所以插入到A[j]后面A[j+1]
        v[j + 1] = key_v;
        w[j + 1] = key_w;
    }
}

void gready_fractional_knapsack(double v[n], double w[n], double W, double x[n])
{
    
    // 初始化都为0,哪个都不装入
    memset(x, 0, sizeof(x));
    // 背包的剩余容量,开始什么都不装
    double c = W;
    // 遍历每个物品
    int i;
    for (i = 0; i < n; i++)
    {
    
        // 如果物品的重量小于等于背包剩余容量,则可装入
        if (w[i] <= c)
        {
    
            // 装入整件物品
            x[i] = 1;
            // 背包剩余容量变少
            c -= w[i];
        }
        // 如果装不进去,那么退出for循环
        else
        {
    
            break;
        }
    }
    // i ≤ n表示exit退出for循环(注意:for成功遍历完每个物品后,i++的最后结果是i=n+1)
    // 如果i ≤ n,说明两种情况,一种是整件物品装不进去但可以装进部分,另一种是背包剩余空间用尽了
    if (i <= n)
    {
    
        // 装入该物品的部分:剩余空间/物品总重
        // 第二种情况进入没事,因为c = 0 时,x(i) = 0
        // 不存在c>=w(i)的情况,要不然就不会exit退出for循环
        x[i] = c / w[i];
    }
}
int main()
{
    
    // 因为算性价比是小数,用double方便
    // 某物品的价值value
    double v[n] = {
    20, 30, 65, 40, 60};
    // 某物品的重量weight
    double w[n] = {
    10, 20, 30, 40, 50};
    // 背包的最大承重量
    double W = 100;
    // 该物品装入背包多少
    double x[n] = {
    };

    // 调整为性价比降序
    costPerformance_insertSort(v, w);

    // 背包算法
    gready_fractional_knapsack(v, w, W, x);

    // 总重
    double my_weight = 0;
    // 总价值
    double my_value = 0;

    // 输出
    for (int i = 0; i < n; i++)
    {
    
        my_weight += w[i] * x[i];
        my_value += v[i] * x[i];
        cout << x[i] << " ";
    }
    cout << endl;

    printf("[my_weight]%lf\n", my_weight);
    printf("[my_value]%lf\n", my_value);

    return 0;
}

三、难:0-1背包问题(0-1 knapsack)

咕咕咕


import java.util.*;

public class Knapsack {
    
	
	class Commodity implements Comparable
	{
    
		int num;
		int values;
		int weight;
		
		public Commodity(int num, int values, int weight)
		{
    
			this.values = values;
			this.weight = weight;
			this.num = num;
		}
		
		@Override
		public int compareTo(Object o) {
      //����
			double vdw1 = (double)this.values/this.weight;
			double vdw2 = (double)((Commodity)o).values/((Commodity)o).weight;
			if(vdw1 > vdw2) return -1;
			else if(vdw1 == vdw2) return 0;
			else return  1;
		}
	}
	
	public static void one_zero_knapsack(Commodity[] commodities, int bag, boolean[] x)
	{
    
		int n = commodities.length;
		boolean[][] memory = new boolean[commodities.length+1][bag+1];
		int[][] c = new int[commodities.length+1][bag+1];
		caculate_c(commodities, c, memory, x, commodities.length,bag);
	}
	
	static void caculate_c(Commodity[] commodities, int[][] c, boolean[][] memory, boolean[] x, int i, int bag)
	{
    
		if(i == 0 || bag ==0) 
		{
    
			c[i][bag] = 0;
			memory[i][bag] = true;
		}
			
		else if(commodities[i-1].weight > bag) 
		{
    
			if(!memory[i-1][bag])
			{
    
				caculate_c(commodities, c, memory, x, i-1, bag);
			}	
			c[i][bag] = c[i-1][bag];
			memory[i][bag] = true;
		}
		else if(i>0 && bag>=commodities[i-1].weight)
		{
    
			if(!memory[i-1][bag-commodities[i-1].weight])
			{
    
				caculate_c(commodities, c, memory, x, i-1, bag-commodities[i-1].weight);
			}
				
			if(!memory[i-1][bag])
			{
    
				caculate_c(commodities, c, memory, x, i-1, bag);
			}
				
			int value1 = c[i-1][bag-commodities[i-1].weight] + commodities[i-1].values;
			int value2 = c[i-1][bag];
			if(value1 > value2)
		    {
    
				x[commodities[i-1].num] = true;
				c[i][bag] = value1;
				memory[i][bag] = true;
		    }  
			else 
			{
    
				c[i][bag] = value2;
				memory[i][bag] = true;
			}
		}
			
	}
	
	public static void fractional_knapsack(Commodity[] commodities, int bag, double[] x)
	{
    
		Arrays.sort(commodities);
		int n = commodities.length;
		for(int i=0; i<n; ++i)
		{
    
			if(bag - commodities[i].weight >= 0) 
			{
    
				bag -= commodities[i].weight;
				x[commodities[i].num] = 1;
			}
			else
			{
    
				x[commodities[i].num] = (double)bag/commodities[i].weight;
				break;
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
    
		
		Knapsack ks = new Knapsack();
		Commodity[] commodities = {
    ks.new Commodity(0,20,10),
                				   ks.new Commodity(1,30,20),
                				   ks.new Commodity(2,65,30),
                				   ks.new Commodity(3,40,40),
                				   ks.new Commodity(4,60,50)};
		//Arrays.sort(commodities);
        int bag = 100;
        //0-1 knapsack
		boolean[] one_zero = new boolean[commodities.length];
		for(int i=0; i<commodities.length; ++i)
		{
    
			one_zero[i] = false;
		}
		Knapsack.one_zero_knapsack(commodities, bag, one_zero);
		System.out.println("0-1 knapsack:");
		for(int i=0; i<commodities.length; ++i)
		{
    
			System.out.println(one_zero[i]);
		}
		//fractional knapsack	
		double[] fra  = new double[commodities.length];
		Knapsack.fractional_knapsack(commodities, bag, fra);
		System.out.println("fractional knapsack:");
		for(int i=0; i<commodities.length; ++i)
		{
    
			System.out.println(fra[i]);
		}
		
	}

}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sandalphon4869/article/details/105943906

智能推荐

java常用的搜索引擎_各大搜索引擎,Java面试题(集合+并发+调优+微服务)_王诗洋的博客-程序员宅基地

Synchronized 用过吗,其原理是什么?你刚才提到获取对象的锁,这个“锁”到底是什么?如何确定对象的锁?什么是可重入性,为什么说 Synchronized 是可重入锁?JVM 对 Java 的原生锁做了哪些优化?48为什么说 Synchronized 是非公平锁?49什么是锁消除和锁粗化?49为什么说 Synchronized 是一个悲观锁?乐观锁的实现原理又是什么?什么是 CAS,它有什...

利用c51进行数模转换并在液晶屏上显示_急求一个基于89C51单片机,用4*4矩阵键盘输入数据,并在LCD1602上显示出来的c语言程序。..._weixin_39538877的博客-程序员宅基地

展开全部#define LCD1602_FLAG#define LCD1602_PORT P0#include#include#define uchar unsigned charsbit lcd1602_rs=P2^0;sbit lcd1602_e=P2^2;sbit lcd1602_rw=P2^1;sbit lcd1602_busy=P0^7;uchar str[]="This is Key ...

matlab 代码 经典例题,MATLAB程序设计及经典例题解析3_天下事一点通的博客-程序员宅基地

MATLAB程序设计用MATLAB语言编写的程序,称为M文件。M文件可以根据调用方式的不同分为两类:命令文件(Script File)和函数文件(Function File)。例3-1 分别建立命令文件和函数文件,将华氏温度f转换为摄氏温度c。程序1:首先建立命令文件并以文件名f2c.m存盘。clear; %清除工作空间中的变量f=input('Input Fahrenheit temperatu...

windows下常用cmd命令_无效格式的博客-程序员宅基地

windows下常用cmd命令新建文件: type nul &gt; test.txt向文件中写入文字:echo ‘Hello, world’ &gt; test.txt重命名文件:rename test.txt test2.txt复制文件:copy test2.txt test3.txt删除文件:del test2.txt新建文件夹命令:md(或者 mkdir) test删除文件夹命令(文件夹需为空): rd test强制删除文件夹(提示信息):rd /s test强制删除文件夹(不提

java linux 当前路径_Java,Linux文件路径_weixin_39816946的博客-程序员宅基地

斜杠和反斜杠正斜杠,又称左斜杠,符号是"/";反斜杠,也称右斜杠,符号是"\"。在Unix/Linux中,路径的分隔采用正斜"/",比如"cd /home/java";而在Windows中,路径分隔采用反斜杠"\",比如"F:\yihong_\book"。我开发是在Windows平台上,所以Java程序配置文件中文件路劲都是用的"\\",而项目是部署在Linux上的,所有文件路劲都是用的"/"。转...

plupload 文件太大 弹出alert_视频格式转换图文教程,MP4音频图片多媒体,免费软件文件剪辑..._weixin_39537977的博客-程序员宅基地

大家好,我是老盖,首先感谢观看本文,本篇文章做的有视频,视频讲述的比较详细,也可以看我发布的视频。视频音频格式转换很多种软件,我个人用了这个软件已经很多年了,在很多年前,那时候转换的软件还不太多,当时他支持的格式比较多,转换效果也不错,就一直用着,现在这几年转换的软件不少了,但是一直还是保留这个软件,今天给大家介绍一下,我这里准备了一个测试视频文件,作为转换测试。软件运行后就是这个界面,左边是选择...

随便推点

c++学习之:根据GetLastError()返回值获取错误信息_weixin_33907511的博客-程序员宅基地

VC中GetLastError()获取错误信息的使用在VC中编写应用程序时,经常需要涉及到错误处理问题。许多函数调用只用TRUE和FALSE来表明函数的运行结果。一旦出现错误,MSDN中往往会指出请用GetLastError()函数来获得错误原因。     可问题是,GetLastError()返回的只是一个双字节数值(DWORD)。OH,MY GOD!目前Win32的出错编号已经从0排到11...

.net core MVC中级教程(三)_weixin_30279315的博客-程序员宅基地

1、对昨天主页不能显示添加的新成员信息bug进行修改2、运用EFCore将其数据写入数据库中1、对昨天主页不能显示添加的新成员信息bug进行修改修改下生命周期,在运行Transient:每一次GetService都会创建一个新的实例Scoped:在同一个Scope内只初始化一个实例 ,可以理解为( 每一个request级别只创建一个实例,同...

jquery ajax方法兼容ie9,Jquery AJAX not working in IE9_姜兴的博客-程序员宅基地

I am writing an ajax web application but for whatever reason when I perform a GET against an internal data service in Internet Explorer 9 (IE9) it does not work. This same call works perfectly fine in...

接口测试 --apipost 如何自定义变量_雨中测试人的博客-程序员宅基地

如何在接口测试工具apipost自定义变量?这个就需要使用apipost自带的脚本功能,有预执行脚本和后执行脚本什么是APIPOST脚本APIPOST脚本是基于JavaScript语言的代码片段,可实现在接口请求或集合测试时添加动态行为。脚本可实现的功能测试(断言)请求返回结果的正确性(后置脚本)。动态修改接口请求参数,如增加接口签名参数等(前置脚本)。接口请求之间传递数据(使用脚本操作变量)。脚本中可以直接请求一个接口地址。APIPOST的脚本分为预执行脚本和后执行脚本。预执行脚本

mysql usage_MySQL数据库表中有usage字段名后的后果_苏白衣的博客-程序员宅基地

一个很奇怪的42000的错误,折腾了我一晚上。。。。我的系统是Spring + SpringMVC + MyBatis结构, 数据库的mapper以及model等文件都是用MyBatisGenerator自动生成的,一切都很快就完成了。 我的表结构module如下:1 mysql&gt;desc module;2 +----------+---------------+------+-----+-...

Java中int的取值范围_第十七签的博客-程序员宅基地

int型的数据字节长度是4,一共是32位,第一位用于表示正负号,其他位的数字组成它所代表的值,例如7的二进制表示形式为: 00000000 00000000 00000000 00000111 当表示负数的时候,则采用的是补码的形式,第一位是1,例如-7的二进制表示为: 11111111 11111111 11111111 11111001 int型数据的取值范围:-2^31—-2^31-1