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 等式后面部分如何编入代码获取,求完善代码,谢谢大神们

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
背包问题-多重背包问题-金明的预算方案
package 动态规划.多重背包问题; import java.util.Scanner; /*  * 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属
如何获得该直线方程?
rn平面上有n个点( n >= 3 ), 求一条直线,使得这n个点到该直线的距离的平方和最小,不能对每个斜率用遍历方法(那样太慢了)。rnrn请教计算几何方面的高手。rnrn(如果给定斜率,算法我倒是知道的)。
@@@ 知道文件名,获得该文件的具体路径.....
我用循环遍历所有文件夹及其子文件夹的方法找到了所要找的文件,可是现在我想得到该文件的具体路径,我用了GetAbsolutePathName 方法来获得具体得路径可是出错了!!!rn我把我做得工程放在“My Documents\yhy\遍历循环找文件\”中,而文件是在E:\歌曲库的文件夹下,我用了GetAbsolutePathName 方法之后,显示的具体路径就为“E:\My Documents\yhy\遍历循环找文件\10042.vox”,其实文件是在“E:\歌曲库\男歌星\原唱\10025.vox”,这个问题怎么解决啊...???rn怎么才能得到正确的具体路径呢?用什么方法呢?rn请各位高手指教!!rn
背包问题-多重背包问题
在01背包的基础上限制了每件物品数量的上限。最多为si个 最简单的思路就是在多一层循环只要不够s同时不超过V就试图往里加代码如下 public class Main { static int V = 5;//总体积为5 static int n = 4;//物品数量为4 static int[] v = {0, 1, 2, 3, 4};//每个物品的体积为vi st...
多重背包问题
多重背包问题 《背包九讲》 有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M i 件可用,每件耗费 的空间是 C i ,价值是 W i 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量,且价值总和最大。 基本算法 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略 微一改即可。 因为对于第 i 种物品有 M i +1 种策略:取 0 件,取 1 件...
我如何获得该属性
我如何或的下面xml的中documentelement的属性id 的值rn我用xmldoc.documentelement.attributes.getnameditem("id").text无法获得该值rn为什么?rn--------------------rn 与家人同住
01背包问题+完全背包问题+多重背包问题
一 01背包问题 1.1题目 有N件物品和一个容量为V 的背包。放入第i件物品耗费的空间是Ci,得到 的价值是Wi。 求解将哪些物品装入背包可使价值总和最大。 1.2 基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不 放。 用子问题定义状态:即F[i, v]表示前i件物品恰放入一个容量为v的背包可以 获得的最大价值。 则其状态转移方程便是: F[i, v] ...
动态规划之背包问题及输出背包具体方案
题型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[...
51nod 多重背包问题
100% 多重背包问题 一个背包,承量有限为W,有n种物体,第i种物体,价值Vi,占用重量为 Wi,且有Ci件,选择物品若干放入背包,使得总重量不超过背包的承重。总价值最大? 输入第1行,2个整数,N和W中间用空格隔开。N为物品的种类,W为背包的容量。(1 <= N <= 100,1 <= W <= 50000) 第2 - N + 1行,每行3个整数,Wi,Pi和Ci分别是物品体积、价值和数量
51nod多重背包问题
多重背包其实就是把01背包和完全背包写成两个函数然后调用一下就行了,当给的空间大于物品个数*它的容量的时候,那么对于这个物品来说相当于完全背包,反之则为01背包#include <iostream>using namespace std; int v[105],price[105],num[105]; long long dp[50005]; void Zero_Pack(int value,int
多重背包问题 I
有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。 接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。 输出格式 输出一个整...
庆功会 多重背包问题c++
庆功会c++动态规划,基础的多重背包问题(@﹏@)~
HDU 2191 多重背包问题
HDU 2191 典型的多重背包问题,题目的链接如下: http://acm.hdu.edu.cn/showproblem.php?pid=2191悼念512汶川大地震遇难同胞——珍惜现在,感恩生活Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission
51nod-【多重背包问题】
#include #include #define LL long long LL f[50000+11]; struct node { int a;//重量 int b;//价值 }arr[50000]; LL max(LL x,LL y) { if(x>y) return x; return y; } int main() { LL n,w; scanf("%lld%ll
多重背包问题(dp)
多重背包问题我们看看有没有办法变成更好的0-1背包问题。 思路1的意思是说我们把第i种物品看成单个的,一个一个的,我们想想二进制,任何一个数都可以由二的幂表示。我们试试看,比如Ci  = 14,我们可以把它化成如下4个物品:重量是Wi,体积是Vi重量是2 * Wi , 体积是2 * Vi重量是4 * Wi , 体积是4 * Vi重量是7 * Wi , 体积是7 * Vi注意最后我们最后我们不能取,...
hdu2191 多重背包问题
解题思路:         典型的多重背包问题,采用二进制思想来解决。 MULTIPLE_PACK(cost,weight,amount) if cost * amount >= V then COMPLETE_PACK(cost,weight) return int k ←1 while k < amount do ZER
51Nod 1086 - 多重背包问题
有N种物品,每种物品的数量为C1,C2......Cn。从中任选若干件放在容量为W的背包里,每种物品的体积为W1,W2......Wn(Wi为整数),与之相对应的价值为P1,P2......Pn(Pi为整数)。求背包能够容纳的最大价值。Input第1行,2个整数,N和W中间用空格隔开。N为物品的种类,W为背包的容量。(1 &amp;lt;= N &amp;lt;= 100,1 &amp;lt;= W &amp;lt;= 5000...
POJ-1276 多重背包问题
Cash Machine     题意:输入第一行cash  N n1 D1 n2 D2 ... nN DN ,D1表示一种面值的零钱,n1表示D1可以使用的数量。一共有N种零钱。需要找出用这些零钱可以组成的不超过cash的最大数额。     这是一道多重背包的问题,和poj-1014 多重背包问题类似,需要先转化成01背包,再用01背包问题的方法求解。转换的代码如下,a[i]是转换前第i个零
51nod 多重背包问题(二进制优化)
有N种物品,每种物品的数量为C1,C2......Cn。从中任选若干件放在容量为W的背包里,每种物品的体积为W1,W2......Wn(Wi为整数),与之相对应的价值为P1,P2......Pn(Pi为整数)。求背包能够容纳的最大价值。 我们可以转化成01背包来做,但是这样很慢。 所以我们可以二进制优化。 一个数a,我们可以按照二进制来分解为1 + 2 + ...
[C++] 完全&多重背包问题
文章目录一·完全背包问题1. 题目2. 思路二·多重背包问题1.题目2.思路 一·完全背包问题 1. 题目 有NNN种物品和一个容量为 VVV 的背包,每种物品都有无限件可用。放入第 iii 种物品的耗费的空间是CiC_iCi​,得到的价值是WiW_iWi​。求解:将哪些物品装入背包,可使这些物品的耗费的空间总和不超过背包容量,且价值总和最大。 2. 思路 题目虽然说得有无限多个,但事实上最多装[...
[多重背包问题] 硬币
硬币 给定N种硬币,其中第 i 种硬币的面值为Ai,共有Ci个。 从中选出若干个硬币,把面值相加,若结果为S,则称“面值S能被拼成”。 求1~M之间能被拼成的面值有多少个。 输入格式 输入包含多组测试用例。 每组测试用例第一行包含两个整数N和M。 第二行包含2N个整数,分别表示A1,A2,…,AN和C1,C2,…,CN。 当输入用例N=0,M=0时,表示输入终止,且该用例无需处理。 输出格式 每...
HDU2844(dp多重背包问题)
解题思路:多重背包问题其实可以转换成01背包问题,但是层数相较于以前会多,所以不能用多层,还是用单层dp,或双层循环dp比较好。就是把以前一个物品的数量用二次幂分解当成多个物品。 #include&amp;lt;cstdio&amp;gt; #include&amp;lt;cstring&amp;gt; #include&amp;lt;algorithm&amp;gt; #define inf 0x3f3f3f3f using namesp...
多重背包问题 II
题目 有N种物品和一个容量是V的背包。 第i种物品最多有si 件,每件体积是vi,价值是wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 输入格式 第一行两个整数,N,V 用空格隔开,分别表示物品种数和背包容积。 接下来有N行,每行三个整数vi,wi,si,用空格隔开,分别表示第ii种物品的体积、价值和数量。 ...
*背包问题(01+完全+多重)
今天是2017/7/11,DCDCBigBig的第二十六篇博文 背包问题应该算是最最基础的DP入门了吧。。。这几天在搞奇怪的DP,无聊来发发背包^_^背包问题01背包(一维优化)#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,v,f[10001],c[10
51nod 多重背包问题 (dp)
输入 第1行,2个整数,N和W中间用空格隔开。N为物品的种类,W为背包的容量。(1 <= N <= 100,1 <= W <= 50000) 第2 - N + 1行,每行3个整数,Wi,Pi和Ci分别是物品体积、价值和数量。(1 输出 输出可以容纳的最大价值。 输入示例 3 6 2 2 5 3 3 8 1 4 1
背包问题(01,完全,多重)
public class Package { public static void main(String[] args) { int W=10; int[] w={2,3,2,5}; int[] v={3,4,5,6}; int[] k={2,1,2,1}; System.out.println(packa...
poj-1014 多重背包问题
Dividing     题意:有一堆大理石,每个石头的价值在1-6之间,每种价格的石头有多个。现在要求将这堆石头分成两份,使得两份的总价值相同,回答是否存在一种方法将可以实现划分。     这是一道多重背包问题,多重背包问题的做法可以是先将它转化为01背包,再用01背包问题的方法继续求解。转化的思路是,将一个价格下的几件物品,组合成多个价格下个一件物品。比如价格2下原来有7件物品(二进制11
HDU2186(多重背包问题)
HDU2186 输入数据首先包含一个正整数C,表示有C组测试用例,每组测试用例的第一行是两个整数n和m(1   Output 对于每组测试数据,请输出能够购买大米的最多重量,你可以假设经费买不光所有的大米,并且经费你可以不用完。每个实例的输出占一行。   Sample Input 1 8 2 2 100 4 4 100 2
多重背包问题的实现
POJ1276 之前看过一遍背包九讲,没有深刻体会,今天碰到了多重背包的模板题=。= Problem:Cash Machine Description A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a reques...
POJ 1267 多重背包问题
背包问题分为三种 0-1 背包问题         每种物品只有一个。 完全背包问题        每种物品无限个。 多重背包问题        每种物品有限个但不止一个。 多重背包问题分为两种解法: 依据0-1 背包性质,我们将有限个的同种物品认为不同,然后按照0-1背包问题解决,这种解法这题超时。 第二种解法,多重背包二进制优化解决。二进制优化解释 背包问题详解:01背包、完全背包、...
多重背包问题 求代码
。rn现在你有M元钱,可以采购N种物品,每种物品最多可以购买Ai件(也可以不购买),rn每购买一件会花费Ci元,并能产生Vi的价值。请算出你能买的物品的最大价值和。rn【输入】rn 输入文件名为prepare.in。rn第一行,两个整数M,N用空格隔开。后面N行,每行三个整数用空格隔开Ai、Ci、Virn【输出】rn 输出文件名为prepare.out。rn一个整数,能买的物品的最大价值和rn【输入输出样例】rnprepare.in prepare.outrn40 4 45rn1 20 5rn2 10 7rn3 15 19rn4 5 1
可视化多重背包问题计算器
名称:Knapsack 类型:可视化多重背包问题计算器 开发工具:vs2008 技术平台:C# 作者:FIA E-mail:iamfia@sina.com 完全开源 仅供参考
多重背包问题,谢谢各位了
3 多重背包问题rn3.1 题目rn有N 种物品和一个容量为V 的背包。第i 种物品最多有Mi 件可用,每件耗费的rn空间是Ci,价值是Wi。求解将物品装入背包可使这些物品的耗费的空间总和不超rn过背包容量,且价值总和最大,输出最大价值总和。rn动态方程为f[i][j]=maxf[i-1][j-k*v[i]]+k*w[i]其中(0=rn#define N 20rnint main()rnrn int n,i,j,w[N],v[N],m[N],f[1000],V;rn scanf("%d",&V); //包的容量 rn scanf("%d",&n); //有几种物品 rn for(i=1;i<=n;i++)rn scanf("%d%d%d",v[i],w[i],m[i]);//物品的所占容积大小,价值,有几件 rn rn for(i=0;i<=V;i++)//初始化 rn f[i]=0;rn rn for(i=1;i<=n;i++)rn rn if(v[i]*m[i]>=V) //完全背包 rn rn for(j=1;j=v[i];j--)rn if(f[j]
相关热词 c++和c#哪个就业率高 c# 批量动态创建控件 c# 模块和程序集的区别 c# gmap 截图 c# 验证码图片生成类 c# 再次尝试 连接失败 c#开发编写规范 c# 压缩图片好麻烦 c#计算数组中的平均值 c#获取路由参数