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

约定不等于承诺〃 2022-07-12 12:41 197阅读 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 条评论，197人围观）

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

相关阅读

相关动态规划-背包问题

动态规划--背包问题

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

相关背包问题-动态规划

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

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

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

背包问题 -------------------- 目录 1. 概述 2. 背包问题：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个

叁歲伎倆/ 2023年06月30日 08:58/ 0 赞/ 78 阅读

相关背包型动态规划——背包问题6

给出一个都是正整数的数组 `nums`，其中没有重复的数。从中找出所有的和为 `target` 的组合个数。示例：输入: nums = [1, 2, 4

阳光穿透心脏的1/2处/ 2022年10月27日 12:06/ 0 赞/ 179 阅读

相关背包型动态规划——背包问题3

给定 `n` 种物品, 每种物品都有无限个. 第 `i` 个物品的体积为 `A[i]`, 价值为 `V[i]`. 再给定一个容量为 `m` 的背包. 问可以装入背包的

傷城~/ 2022年10月27日 12:06/ 0 赞/ 195 阅读

相关背包型动态规划——背包问题1

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\] 示例：样例 1: 输入: [3,4,8,5]

旧城等待，/ 2022年10月27日 06:30/ 0 赞/ 175 阅读

相关背包型动态规划——背包问题2

有 `n` 个物品和一个大小为 `m` 的背包. 给定数组 `A` 表示每个物品的大小和数组 `V` 表示每个物品的价值. 问最多能装入背包的总价值是多大? 样例

忘是亡心i/ 2022年10月27日 06:29/ 0 赞/ 172 阅读

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

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

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

相关背包问题，动态规划

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

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

相关动态规划背包问题

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

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