动态规划——背包问题笔记

约定不等于承诺〃 2022-07-12 12:41 156阅读 0赞

理解动态规划先从：

[通过金矿模型介绍动态规划][Link 1]

之后，可以通过下面博客的表来理解：

[动态规划之01背包问题（最易理解的讲解）][01]

程序实现时，思路和画表时相同

给出程序：http://blog.csdn.net/littlethunder/article/details/26575417

### 01背包的状态转换方程 f\[i,j\] = Max\{ f\[i-1,j-Wi\]+Pi( j >= Wi ), f\[i-1,j\] \} ###

# -*- coding: utf-8 -*-
    # n为物品数量
    # c为背包重量
    # w为每个物品重量
    # v为每个物品价值
    def bag(n, c, w, v):  
    	res=[[-1 for j in range(c+1)] for i in range(n+1)]
    	for j in range(c+1):
    		res[0][j] = 0
    	for i in range(1, n+1):
    		for j in range(1, c+1):
    			res[i][j] = res[i-1][j]
    			if j >= w[i-1] and res[i][j] < res[i-1][j-w[i-1]] + v[i-1]:
    				res[i][j] = res[i-1][j-w[i-1]] + v[i-1]
    	return res
    
    
    def show(n, c, w, res):
    	print('最大价值为:',res[n][c])
    	x = [False for i in range(n)]
    	j = c
    	for i in range(1,n+1):
    		if res[i][j] > res[i-1][j]:
    			x[i-1] = True
    			j -= w[i-1]
    	print('选择的物品为:')
    	for i in range(n):
    		if x[i]:
    			print('第',i,'个,',end='')
    	print('')
    
    if __name__ == '__main__':
    	n = 4
    	c = 10
    	w = [5,2,8,3]
    	v = [7,3,10,4]
    	res = bag(n,c,w,v)
    	show(n,c,w,res)

给出程序

[Link 1]: http://www.cnblogs.com/SDJL/archive/2008/08/22/1274312.html
[01]: http://blog.csdn.net/mu399/article/details/7722810

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划-背包问题

动态规划--背包问题

悠悠/ 2024年04月23日 20:02/ 0 赞/ 19 阅读

相关背包问题-动态规划

[背包问题九讲][Link 1] [背包问题参考博客][Link 2] 文章目录介绍: 背包问题 01背包问题

逃离我推掉我的手/ 2023年08月17日 17:42/ 0 赞/ 62 阅读

相关 java 动态规划（背包问题）

-------------------- java 动态规划（背包问题） \\\\\\\\\\\\\\\\\\\\\\\\ 背包问题问题描述

「爱情、让人受尽委屈。」/ 2022年11月21日 11:23/ 0 赞/ 158 阅读

相关动态规划——背包问题笔记

理解动态规划先从： [通过金矿模型介绍动态规划][Link 1] 之后，可以通过下面博客的表来理解： [动态规划之01背包问题（最易理解的讲解）][01] 程序实现时，

约定不等于承诺〃/ 2022年07月12日 12:41/ 0 赞/ 157 阅读

相关 01背包问题（动态规划）

总结——01背包问题（动态规划算法） 0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。问：应该如何选择装入背

ゞ浴缸里的玫瑰/ 2022年05月19日 11:22/ 0 赞/ 241 阅读

相关背包问题，动态规划

将下面四个重量的物品1，2，2，3 价值分别是9，3，3，6 装进重量为4的背包中，使得背包的重量不超过4，并且价值最大。 include<iostream>

左手的ㄟ右手/ 2022年02月28日 14:50/ 0 赞/ 232 阅读

相关动态规划 -- 01 背包问题

问题描述：假设现有容量m kg的背包，另外有n个物品，重量分别为w\[1\] w\[2\] ... w\[i\] （kg）,价值分别为p\[1\] p\[2\] ... p

浅浅的花香味﹌/ 2022年02月26日 00:10/ 0 赞/ 325 阅读

相关【动态规划】01背包问题

说明前面用`动态规划`解决了正则表达式的问题，感觉还是不过瘾，总觉得对于`动态规划`的理解还没有到位，所以趁热打铁，继续研究几个`动态规划`的经典问题，希望能够借此加深

一时失言乱红尘/ 2022年02月13日 20:09/ 0 赞/ 324 阅读

相关动态规划背包问题

[本篇博文参考此博文，该博文PPT非常有助理解][PPT] > 问题描述： > 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背

傷城~/ 2021年09月11日 08:42/ 0 赞/ 370 阅读

相关动态规划-01背包问题

文章目录题目背景题目分析状态转移方程对应价值表具体代码题目背景 > 现在有四个物品

我不是女神ヾ/ 2021年09月07日 06:03/ 0 赞/ 433 阅读