文档章节

动态规划的用法——01背包问题

自由的角马
 自由的角马
发布于 2015/01/10 13:57
字数 662
阅读 21
收藏 0

动态规划的用法——01背包问题

 

问题主题:著名的01背包问题

问题描述:

n个重量和价值分别为wivi的物品,现在要从这些物品中选出总重量不超过W的物品,求所有挑选方案中的价值最大值。

限制条件:

1<=N<=100

1<=wvi<=100

1<=wi<=10000

样例:

输入

N=4

W[N] = {2, 1, 3, 2}

V[N] = {3, 2, 4, 2}

输出

W = 5(选择013)

 

 

【解法一】

解题分析:

    用普通的递归方法,对每个物品是否放入背包进行搜索

程序实现:

C++

#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"
 
using namespace std;
 
const int N = 4;
const int W = 5;
int weight[N] = {2, 1, 3, 2};
int value[N] = {3, 2, 4, 2};
int solve(int i, int residue) 
{
int result = 0;
if(i >= N)
return result;
if(weight[i] > residue)
result = solve(i+1, residue);
else 
{
result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]);
}
 
}
 
int main() {
int result = solve(0, W);
cout << result << endl;
return 0;
}

 

 

【解法

解题分析:

    用记录结果再利用的动态规划的方法,上面用递归的方法有很多重复的计算,效率不高。我们可以记录每一次的计算结果,下次要用时再直接去取,以提高效率

程序实现:

C++

#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"

using namespace std;

const int N = 4;
const int W = 5;
int weight[N] = {2, 1, 3, 2};
int value[N] = {3, 2, 4, 2};
int record[N][W];
void init()
{
	for(int i = 0; i < N; i ++)
	{
		for(int j = 0; j < W; j ++) 
		{
			record[i][j] = -1;
		}
	}
}

int solve(int i, int residue) 
{
	if(-1 != record[i][residue])
		return record[i][residue];
	int result = 0;
	if(i >= N)
		return result;
	if(weight[i] > residue)
	{
		record[i + 1][residue] = solve(i+1, residue);
		
	}
	else 
	{
		result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]);
	}
	return record[i + 1][residue] = result;
}

int main() {
	init();
	int result = solve(0, W);
	cout << result << endl;
	return 0;
}

Java

package greed;

/**
 * User: luoweifu
 * Date: 14-1-21
 * Time: 下午5:13
 */
public class Knapsack {
	private int maxWeight;
	private int[][] record;
	private Stuff[] stuffs;

	public Knapsack(Stuff[] stuffs, int maxWeight) {
		this.stuffs = stuffs;
		this.maxWeight = maxWeight;
		int n = stuffs.length + 1;
		int m = maxWeight+1;
		record = new int[n][m];
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
				record[i][j] = -1;
			}
		}
	}
	public int solve(int i, int residue) {
		if(record[i][residue] > 0) {
			return record[i][residue];
		}
		int result;
		if(i >= stuffs.length) {
			return 0;
		}
		if(stuffs[i].getWeight() > residue) {
			result = solve(i + 1, residue);
		} else {
			result = Math.max(solve(i + 1, residue),
				 solve(i + 1, residue - stuffs[i].getWeight()) + stuffs[i].getValue());
		}
		record[i][residue] = result;
		return result;
	}

	public static void main(String args[]) {
		Stuff stuffs[] = {
			new Stuff(2, 3),
			new Stuff(1, 2),
			new Stuff(3, 4),
			new Stuff(2, 2)
		};
		Knapsack knapsack = new Knapsack(stuffs, 5);
		int result = knapsack.solve(0, 5);
		System.out.println(result);
	}
}

class Stuff{
	private int weight;
	private int value;

	public Stuff(int weight, int value) {
		this.weight = weight;
		this.value = value;
	}

	int getWeight() {
		return weight;
	}

	void setWeight(int weight) {
		this.weight = weight;
	}

	int getValue() {
		return value;
	}

	void setValue(int value) {
		this.value = value;
	}
}


 

 

算法复杂度:

    时间复杂度O(NW)

本文转载自:http://blog.csdn.net/luoweifu/article/details/18509317

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
动态规划——背包问题(01背包、完全背包、多重背包)

参考: 背包九讲——哔哩哔哩 背包九讲 01背包问题 01背包问题 描述: 有N件物品和一个容量为V的背包。 第i件物品的体积是vi,价值是wi。 求解将哪些物品装入背包,可使这些物品的总体积不超...

pandaWaKaKa
08/25
0
0
前端与算法-动态规划之01背包问题浅析与实现

去年因为工作中的某个应用场景,需要使用到动态规划,为此花了些时间啃了啃背包算法 为啥去年的东西,今年才写粗来,也许大概是懒吧 动态规划 Dynamic Programming 先简单说下什么是动态规划...

小黎也
2018/07/31
0
0
【转】经典算法总结——背包问题(java实现)【已完结】

问题描述: 一个背包的总容量为V,现在有N类物品,第i类物品的重量为weight[i],价值为value[i] 那么往该背包里装东西,怎样装才能使得最终包内物品的总价值最大。这里装物品主要由三种装法: 1、...

Jinlong_Xu
07/22
0
0
算法:Dynamic Programing

一、动态规划干嘛的 二、可以解决哪些问题 动态规划一般可分为:线性动规,区域动规,树形动规,背包动规四类。 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等; 区域动规:石子...

猫咪要感冒
2016/10/09
1
0
动态规划 &

一、 动态规划(Dp问题):解决问题的关键点 1) 递推公式:(最有子结构) 2) 数据的初始化 用例分析: a. 01 背包的问题(Knapsack Problem) 定义: 一个背包的容量V; 存在N个物品:w[i...

Playboy002
2015/07/17
57
0

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
15
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
15
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部