python多重背包问题,已有最佳值,如何获得该最佳的具体方案 5C

def MultiplePack(N, V, weight, value, num):
"""
多重背包问题(每个物品都有次数限制)
:param N: 物品个数, 如 N=5
:param V: 背包总容量, 如V=15
:param weight: 每个物品的容量数组表示, 如weight=[5,4,7,2,6]
:param value: 每个物品的价值数组表示, 如value=[12,3,10,3,6]
:param num: 每个物品的个数限制,如num=[2,4,1,5,3]
:return: 返回最大的总价值
"""

# 初始化f[N+1][V+1]为0,f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
f = [[0 for col in range(V + 1)] for row in range(N + 1)]
g = [[0 for col in range(V + 1)] for row in range(N + 1)]
for i in range(1, N+1):
    for j in range(1, V+1):
        # 对于物品i最多能取的次数是j/weight[i-1]与num[i-1]中较小者
        max_num_i = int(min(j/weight[i-1], num[i-1]))
        f[i][j] = f[i - 1][j]  # 初始取k=0为最大,下面的循环是把取了k个物品i能获得的最大价值赋值给f[i][j]
        for k in range(max_num_i+1):
            if f[i][j] < f[i-1][j-k*weight[i-1]]+k*value[i-1]:
                f[i][j] = f[i-1][j-k*weight[i-1]]+k*value[i-1]  # 状态方程
max_value = f[N][V]
return max_value

print(MultiplePack(3,1585,[807,797,787],[807,797,787],[6,5,2]))

以上为获得最佳值的代码,运行后为1584,但还想知道具体方案是怎么样的比如上面这个例子里 1584 = 797*1+787*1 等式后面部分如何编入代码获取,求完善代码,谢谢大神们

0

1个回答

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
动态规划:《部分背包问题》-python实现
接上两篇 部分背包问题:有n种重量和价值分别为Wi和Vi的物品。从这些物品中挑选出总重量不超过w的物品,第i种物品最多选mi个,求所有挑选方案中价值总和的最大值。 将部分背包问题转换成01背包问题进行求解。 import sys def track(d, c, w): x = [] for i in range(1, len(w)): if d[i][c...
背包问题问法变化之---输出方案
/* 背包问题之问法变化--输出方案 输出方案:记录下每个状态的最优值是由哪一项推出来的. 具体操作是:用一个mark数组记录其是否选择或者选几件等. 0-1背包就是记录其是否要选择,而完全背包和多重背包就是记录要选几件,当然也可能不选该种物品. */ #include #include int main() { int N,V; while(scanf("%d%d
动态规划之背包问题及输出背包具体方案
题型1:LintCode 92. 背包问题题目:在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]。分析:dp[i][j]:当背包总重量为j且目前有i个物品时,背包最多装满dp[i][j]的空间。        状态转移方程为:dp[i][j]=max{dp[i-1][j-A[i-1]]+A[i-1], dp[i-1][j]},其中dp[i-1][j-A[...
背包问题----完全背包(最优方案总数分析及实现)
本人博文《背包问题——“完全背包”详解及实现(包含背包具体物品的求解)》中已详细谈过完全背包问题,同时在博文《背包问题——“01背包”最优方案总数分析及实现》中也总结过01背包的最优方案总数的实现。这里我们模仿01背包最优方案总数方法给出完全背包的最优方案求解方法。             重写完全背包的动态规划的状态及状态方程:         完全背包是在N种物品中选取若干件
背包问题之:01背包、完全背包、多重背包(本文源码可求物品放置列表)
不得不说,背包问题非常经典也非常有趣。理解起来可能难点,但懂了之后会发现其实很简单。
多重背包问题 II
有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。 接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。 输出格式 输出一个整...
背包问题、决策树及python实现
背包问题是最优解问题中的一种,我们先来看一下最优解的定义:在特定要求下,按特定需求得出最优结果。 按照这个定义我们做一下下面的分析,有以下一些特征: 特定要求,比如:某一个空间有固定容量,或固定负重 特定需求,需要放入多种类型东西,这些东西有重量、价值、体积等属性 最优结果,比如:最大价值,最多数量, ...
多重背包问题 可行性问题O(V N) 算法
问题:有n种不同大小的数字ai,每种各mi个。判断是是否可以从这些数字中选出若干个使他们的和为k。 算法一#include<stdio.h> int a[100],m[100]; bool dp[100][100]; int main() { int n,w; scanf("%d%d",&n,&w); for(int i=0;i<n;i++) scanf("
中级篇——背包问题3(多重背包)
上一篇讲的完全背包是指在所有物品件数无限多的情况下选择最值,现在引申出多重背包问题,即各物品个数均有限且不一定相同,求轙类情况下的最值。
动态规划--背包问题(01、完全、多重)
01背包: 有n 种不同的物品,每个物品有两个属性,size 体积,value 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。   例:编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,每件物品数量只有一个,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和? 考虑f[5][10]即表示为5种都...
算法——背包问题 01背包+完全背包+多重背包
01背包:https://biancheng.love/problem/51/index 有n 种不同的物品,每个物品有两个属性,size 体积,value 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。   [cpp] view plain copy int f[w+1];   //f[x] 表示背包容量为x 时
C++动态规划之背包问题之多重背包求方案数之 : 新年去世(趣事)之打牌 运用递归+数组输出多重背包的路径(用了哪些物品)
此题是一道很简单的多重背包的题。相信只要有点DP基础的同学都可以打出此题的部分解。但此题的重点在于它还要要求输出在到达目标的情况下输出相应的路径。(这种方法是我自己根据以前所学琢磨出来的,可能有点纰漏,见谅。我还没有看过题解,所以知不知道是不是正解)。 话说看了看别人的题解,我的这篇博客应该算是比较详细了的吧。
背包问题——“01背包”最优方案总数的求解
回忆一下01背包的动态规划状态及状态方程:  设背包容量为M,一共有N件物品,每件物品质量为weight[i],每件物品的价值为value[i]。 1) 子问题定义:dp[i][j]表示前i件物品中选取若干件物品放入剩余容量为j的背包中所能得到的最大价值。 2) 根据第i件物品放或不放进行决策。   详细细节就不再多说了,我们直接进入正题。 在这里的话,最优方案总数就是物品总价值最大的
背包问题(0-1背包、完全背包、多重背包)详解
背包问题一个背包总容量为V, 现在有N个物品, 第i个物品体积为weight[i], 价值为value[i], 现在往背包里面装东西, 怎样装才能使背包内物品总价值最大.求解思路利用动态规划求最优值的方法,当前状态的最优值可以转化成上一个状态的最优值,与上一个状态转移到当前状态代价的组合求最值。具体问题分类背包问题可以根据物品个数的限制,有多种情况0-1背包,完全背包,多重背包。0-1背包问题0-1
多重背包的二进制优化问题
一般的思路: 把多重背包转化为01背包,但这样时间复杂度是不变的,依然会TLE。 二进制优化: 把第 i 种物品的 num【i】 分为 数个新的物品: 分配为: 1,2,4.....2^c  (2^c &amp;lt; num[ i ]) 剩下的数量都可以由这些二进制组合而成。 CODE(以51NOD1086为例): #include &amp;lt;cstdio&amp;gt; int n,m,dp[5...
动态规划-背包问题python实现
背包问题解析 python实现: #0-1背包问题 ''' 四样物体:wight:[2,3,4,5] value:[3,4,5,6] bag capacity:8 ''' import numpy as np def dpbag(weight, value, capacity): #创建二维数组保存 results = np.zeros((...
01背包,完全背包,多重背包问题详细介绍以及源代码实现
背包问题 部分内容转载自:http://www.cppblog.com/tanky-woo/archive/2010/07/31/121803.html 背包的基本模型就是给你一个容量为V的背包 在一定的限制条件下放进最多(最少?)价值的东西 一般常用动态规划,存在以前状态向当前状态的一个转换,先求出之前状态的最优解,然后根据之前的状态得到现在状态的最优解。 常见的有
动态规划-03多重背包
紧接前面一篇,讲一下“多重背包”问题,该问题与“完全背包”相比,在每个物品的选取次数上给出了限定,即选取次数k不能无限的增大,其方程和“完全背包”的极度相似,只是k的限定条件发生了变化。 c[i][j] = max(c[i-1][j-(k*w[i-1])] + k*v[i-1], c[i-1][j]) (0 &lt;= k &lt;= counts[i]) 其中,counts[i]表示第i件...
动态规划第二讲——完全背包与多重背包问题
上一节,我们讨论了01背包问题,说明了*递归与分治法 与 动态规划DP的区别和联系,介绍了缓存的概念*。以下,我们用DC、DP、cache分别表示分治法、动态规划和缓存。本节,我们讨论01背包的另外两种形似—— 完全背包和多重背包问题,分析DP问题的另外一些情况。 例一:完全背包问题 同样有n种价值和重量分别为weight[i] and value[i], 背包大小W。限制条
多重背包--二进制优化
问题描述: 有N种物品和一个容量为V的背包。第 i 种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 问题分析: 1.初步: 多重背包最朴素的思想就是将所有的物品(不管同不同一类)都看不同的种类,进行01背包的求解。另也可以看做完全背包的变形:第 i 种物品可以取0件、取1件……取n[i]件。
多重背包问题的三种复杂度解法,O(n * w * c)、O(n*w*log c)和O(n * w)。
吹水:初一的时候就遇到了要求快速解决多重背包问题的题目,当时没有总结的习惯,结果最近遇到的时候还有些懵,感觉基础不是很牢固,需要巩固一下,在这里写一下自己对题目中的两种做法的理解。O(n * w *c)解法:相信不用解释这个解法大家都懂,之所以列出来是为了作为后面的参考。#define fo(i, x, y) for(int i = x; i <= y; i ++) #define fd(i, x,
多重背包 java实现
package eg.nk_mt; import java.util.Scanner; /** * 多重背包 * 多重和完全更接近,多了数量的限制,用一个count[n]计数数组来限制物品i的数量。 * 当放入第i个物品是较优值的时候,count[i]=count[j-weight[i]]+1(j 的含义:); * 这样做是因为,放入第i个物品的操作是基于count[j-weight[
多重背包问题及优化详解
转自我的博客:Armin's blog
各种背包问题详解
转载于:http://blog.sina.com.cn/s/blog_8cf6e8d90100zldn.html P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。   基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放
01背包、完全背包、多重背包问题的C++实现及路径记录
这里主要实现路径记录,只求最值问题移步 01背包、完全背包、多重背包问题的C++实现 以下均打印输出路径,即装入背包的物品序号,和最大值。01背包问题#include <iostream> #include<algorithm>using namespace std;int main() { int total_weight = 10; int w[6] = { 0,5,4,3,
01背包问题python递归实现
递归是个好东西,任何具有递归性质的问题通过函数递归调用会变得很简单。一个很复杂的问题,几行代码就能搞定。   最简单的递归问题:现有重量为weight的包,有若干重量分别为W1,W2.....Wn的物品,试问能否从物品中选出若干件而且重量   刚好为weight?   weight具体是怎么构成的,有下面两种情况(假设挑选到Wn时,刚好够weight):   1. 从Wn-1开始就已经够w
经典背包问题 01背包+完全背包+多重背包
01 背包 有n 种不同的物品,每个物品有两个属性,size 体积,value 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。           int f[w+1];   //f[x] 表示背包容量为x 时的最大价值           for (int i=0; i             for (int j=w; j>=size[i]; j--)
动态规划解二维多重背包问题
背包问题 背包问题是一个很经典的算法问题,根据其复杂程度不同又可分为01背包问题、完全背包问题、多重背包问题、二维背包问题等等。本文讲一讲二维多重背包问题的动态规划解法。 01背包问题 有N件物品和一个容量为V的背包。第i件物品的体积是a[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大 完全背包问题 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品...
多重部分和问题(多重背包+二进制优化)
时间限制: 1 Sec  内存限制: 64 MB提交: 18  解决: 14 题目描述 有n种不同大小的数字,每种各个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。 输入 首先是一个正整数T(1接下来是T组数据 每组数据第一行是一个正整数n(1 第二行是n个不同大小的正整数ai(1第三行是n个正整数mi(1 第四
51nod 多重背包问题(二进制优化)
有N种物品,每种物品的数量为C1,C2......Cn。从中任选若干件放在容量为W的背包里,每种物品的体积为W1,W2......Wn(Wi为整数),与之相对应的价值为P1,P2......Pn(Pi为整数)。求背包能够容纳的最大价值。 我们可以转化成01背包来做,但是这样很慢。 所以我们可以二进制优化。 一个数a,我们可以按照二进制来分解为1 + 2 + 4 + 8 …… +2^n + 剩...
hdu 2126 (背包问题之求方案数)
Buy the souvenirs Time Limit: 10000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2156    Accepted Submission(s): 820 Problem Description When the
动态规划-----背包问题-----01背包,完全背包,多重背包
首先把三种情况放在一起来看: 01背包(ZeroOnePack):  有N件物品和一个容量为V的背包。(每种物品均只有一件)第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费
背包问题的动态规划算法和fptas
背包问题instance:给定n个item,i=1,2,…,ni=1,2,\dots,n; weights w1,w2,…,wn∈Z+w_1,w_2,\dots,w_n\in Z^{+}; values v1,v2,…,vn∈Z+v_1,v_2,\dots,v_n\in Z^{+}, 给定背包容量B∈Z+B\in Z^+; 需要找到一个集合S∈{1,2,…,n}S\in\{1,2,\dots,n\}
nyoj106_背包问题(贪心or多重背包解法)
原题链接》》》多重背包解法:三种背包问题模板链接》》》#include<stdio.h> #include<string.h> #define Nmax 11 int v[Nmax]; int w[Nmax]; int dp[21]; int m; void zobag(int v,int w){ for(int i=m;i>=w;i--) if(dp[i]<dp[i-w]+v)
51 Nod 1086 多重背包问题(单调队列优化)
1086 背包问题 V2  基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 有N种物品,每种物品的数量为C1,C2......Cn。从中任选若干件放在容量为W的背包里,每种物品的体积为W1,W2......Wn(Wi为整数),与之相对应的价值为P1,P2......Pn(Pi为整数)。求背包能够容纳的最大价值。 Input 第1行,...
多重背包问题(dp)
多重背包问题我们看看有没有办法变成更好的0-1背包问题。 思路1的意思是说我们把第i种物品看成单个的,一个一个的,我们想想二进制,任何一个数都可以由二的幂表示。我们试试看,比如Ci  = 14,我们可以把它化成如下4个物品:重量是Wi,体积是Vi重量是2 * Wi , 体积是2 * Vi重量是4 * Wi , 体积是4 * Vi重量是7 * Wi , 体积是7 * Vi注意最后我们最后我们不能取,...
[Sicily Coins] 动态规划 多重背包问题
Coins多重背包问题的解题思路
背包问题【01、完全(恰好or不超过)、多重】【尚未整理完】
背包问题 以下整理自:背包问题九讲笔记_01背包 摘自Tianyi Cui童鞋的《背包问题九讲》,稍作修改,方便理
多重背包:经典DP问题( 基本/二进制优化/单调队列优化 )
目录 基本方法 **二进制优化 *****单调队列优化 多重背包问题描述:介于01背包和完全背包问题之间,每种物品的最大选取数目都是已知的。 对于一定数量( i )的物品有一个容量为( j )的背包,每个物品都有自己的容量( k )、价值(value)和数目( cnt )。在保证物品容量之和不大于背包容量的前提下,如何选取物品得到最大价值? 基本方法: *NEW*:测试题链接(基本方...
背包九讲之多重背包问题
背包九讲之多重背包问题注意事项:        多重背包的理解请建立在01背包与完全背包的基础上,在了解01背包与完全背包后,多重背包即可不攻自破。 背包九讲 01背包 完全背包 多重背包
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 python最佳入门教程 如何网页制作已有视频