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实现
接上两篇nn部分背包问题:有n种重量和价值分别为Wi和Vi的物品。从这些物品中挑选出总重量不超过w的物品,第i种物品最多选mi个,求所有挑选方案中价值总和的最大值。nn将部分背包问题转换成01背包问题进行求解。nnnimport sysnnndef track(d, c, w):n x = []n for i in range(1, len(w)):n if d[i][c...
动态规划之背包问题及输出背包具体方案
题型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背包、完全背包、多重背包(本文源码可求物品放置列表)
不得不说,背包问题非常经典也非常有趣。理解起来可能难点,但懂了之后会发现其实很简单。
多重背包问题 可行性问题O(V N) 算法
问题:有n种不同大小的数字ai,每种各mi个。判断是是否可以从这些数字中选出若干个使他们的和为k。 n算法一#include<stdio.h>nint a[100],m[100];nbool dp[100][100];nint main()n{n int n,w;n scanf("%d%d",&n,&w);n for(int i=0;i<n;i++)n scanf("
背包问题、决策树及python实现
n 背包问题是最优解问题中的一种,我们先来看一下最优解的定义:在特定要求下,按特定需求得出最优结果。 n 按照这个定义我们做一下下面的分析,有以下一些特征:n n n 特定要求,比如:某一个空间有固定容量,或固定负重n 特定需求,需要放入多种类型东西,这些东西有重量、价值、体积等属性n 最优结果,比如:最大价值,最多数量,n n...
多重背包问题
 nnnnnnnnn#include &amp;lt;bits/stdc++.h&amp;gt;nnusing namespace std;nnstruct En{n int w; //体积n int v; //重量n} lis[2001];nnint dp[101];nnint main()n{n int T,n,m;n int p,h,k;n int i,j;n int...
算法——背包问题 01背包+完全背包+多重背包
01背包:https://biancheng.love/problem/51/indexnnn有n 种不同的物品,每个物品有两个属性,size 体积,valuen 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。  nnnnnn[cpp] viewn plain copynnnnnnnint f[w+1];   //f[x] 表示背包容量为x 时
背包问题(0-1背包、完全背包、多重背包)详解
背包问题一个背包总容量为V, 现在有N个物品, 第i个物品体积为weight[i], 价值为value[i], 现在往背包里面装东西, 怎样装才能使背包内物品总价值最大.求解思路利用动态规划求最优值的方法,当前状态的最优值可以转化成上一个状态的最优值,与上一个状态转移到当前状态代价的组合求最值。具体问题分类背包问题可以根据物品个数的限制,有多种情况0-1背包,完全背包,多重背包。0-1背包问题0-1
中级篇——背包问题3(多重背包)
上一篇讲的完全背包是指在所有物品件数无限多的情况下选择最值,现在引申出多重背包问题,即各物品个数均有限且不一定相同,求轙类情况下的最值。
C++动态规划之背包问题之多重背包求方案数之 : 新年去世(趣事)之打牌 运用递归+数组输出多重背包的路径(用了哪些物品)
此题是一道很简单的多重背包的题。相信只要有点DP基础的同学都可以打出此题的部分解。但此题的重点在于它还要要求输出在到达目标的情况下输出相应的路径。(这种方法是我自己根据以前所学琢磨出来的,可能有点纰漏,见谅。我还没有看过题解,所以知不知道是不是正解)。nn话说看了看别人的题解,我的这篇博客应该算是比较详细了的吧。
动态规划--背包问题(01、完全、多重)
01背包:nn有n 种不同的物品,每个物品有两个属性,size 体积,value 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。  nn例:编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,每件物品数量只有一个,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?nn考虑f[5][10]即表示为5种都...
多重背包的二进制优化问题
一般的思路:nn把多重背包转化为01背包,但这样时间复杂度是不变的,依然会TLE。nn二进制优化:nn把第 i 种物品的 num【i】 分为 数个新的物品:n分配为:nn1,2,4.....2^c  (2^c &amp;lt; num[ i ])nn剩下的数量都可以由这些二进制组合而成。nnCODE(以51NOD1086为例):nnn#include &amp;lt;cstdio&amp;gt;nint n,m,dp[5...
动态规划-03多重背包
紧接前面一篇,讲一下“多重背包”问题,该问题与“完全背包”相比,在每个物品的选取次数上给出了限定,即选取次数k不能无限的增大,其方程和“完全背包”的极度相似,只是k的限定条件发生了变化。nnnc[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])nn其中,counts[i]表示第i件...
多重背包--二进制优化
问题描述:n有N种物品和一个容量为V的背包。第 i 种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。nnn问题分析:n1.初步:n多重背包最朴素的思想就是将所有的物品(不管同不同一类)都看不同的种类,进行01背包的求解。另也可以看做完全背包的变形:第 i 种物品可以取0件、取1件……取n[i]件。
多重背包 java实现
package eg.nk_mt;nnimport java.util.Scanner;nn/**n * 多重背包n * 多重和完全更接近,多了数量的限制,用一个count[n]计数数组来限制物品i的数量。n * 当放入第i个物品是较优值的时候,count[i]=count[j-weight[i]]+1(j 的含义:);n * 这样做是因为,放入第i个物品的操作是基于count[j-weight[
背包问题(01,完全,多重)
public class Package {n public static void main(String[] args) {n int W=10;n int[] w={2,3,2,5};n int[] v={3,4,5,6};n int[] k={2,1,2,1};n System.out.println(packa...
01背包、完全背包、多重背包问题的C++实现及路径记录
这里主要实现路径记录,只求最值问题移步n 01背包、完全背包、多重背包问题的C++实现n以下均打印输出路径,即装入背包的物品序号,和最大值。01背包问题#include <iostream>n#include<algorithm>using namespace std;int main()n{n int total_weight = 10;n int w[6] = { 0,5,4,3,
多重背包问题的三种复杂度解法,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 ++)n#define fd(i, x,
01背包问题python递归实现
递归是个好东西,任何具有递归性质的问题通过函数递归调用会变得很简单。一个很复杂的问题,几行代码就能搞定。rn  最简单的递归问题:现有重量为weight的包,有若干重量分别为W1,W2.....Wn的物品,试问能否从物品中选出若干件而且重量rn  刚好为weight?rn  weight具体是怎么构成的,有下面两种情况(假设挑选到Wn时,刚好够weight):rn  1. 从Wn-1开始就已经够w
51nod 多重背包问题(二进制优化)
有N种物品,每种物品的数量为C1,C2......Cn。从中任选若干件放在容量为W的背包里,每种物品的体积为W1,W2......Wn(Wi为整数),与之相对应的价值为P1,P2......Pn(Pi为整数)。求背包能够容纳的最大价值。nn我们可以转化成01背包来做,但是这样很慢。nn所以我们可以二进制优化。nn一个数a,我们可以按照二进制来分解为1 + 2 + 4 + 8 …… +2^n + 剩...
动态规划-背包问题python实现
背包问题解析 npython实现:nnnn#0-1背包问题n'''n四样物体:wight:[2,3,4,5]n value:[3,4,5,6]n bag capacity:8n'''nimport numpy as npndef dpbag(weight, value, capacity):nn #创建二维数组保存n results = np.zeros((...
动态规划解二维多重背包问题
背包问题nn背包问题是一个很经典的算法问题,根据其复杂程度不同又可分为01背包问题、完全背包问题、多重背包问题、二维背包问题等等。本文讲一讲二维多重背包问题的动态规划解法。nnnn01背包问题nn有N件物品和一个容量为V的背包。第i件物品的体积是a[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大nnnn完全背包问题nn有N种物品和一个容量为V的背包,每种物品都有无限件可用。第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\}
hdu 2126 (背包问题之求方案数)
Buy the souvenirsrnTime Limit: 10000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)rnTotal Submission(s): 2156    Accepted Submission(s): 820rnrnrnrnProblem DescriptionrnrnWhen the
多重背包:经典DP问题( 基本/二进制优化/单调队列优化 )
目录nn基本方法nn**二进制优化nn*****单调队列优化nn多重背包问题描述:介于01背包和完全背包问题之间,每种物品的最大选取数目都是已知的。nn对于一定数量( i )的物品有一个容量为( j )的背包,每个物品都有自己的容量( k )、价值(value)和数目( cnt )。在保证物品容量之和不大于背包容量的前提下,如何选取物品得到最大价值?nn基本方法:nn*NEW*:测试题链接(基本方...
[Sicily Coins] 动态规划 多重背包问题
Coins多重背包问题的解题思路
背包问题【01、完全(恰好or不超过)、多重】【尚未整理完】
背包问题nnnnnn以下整理自:背包问题九讲笔记_01背包nnnnn摘自Tianyi Cui童鞋的《背包问题九讲》,稍作修改,方便理
[C++] 完全&多重背包问题
文章目录一·完全背包问题1. 题目2. 思路二·多重背包问题1.题目2.思路n一·完全背包问题n1. 题目n有NNN种物品和一个容量为 VVV 的背包,每种物品都有无限件可用。放入第 iii 种物品的耗费的空间是CiC_iCi​,得到的价值是WiW_iWi​。求解:将哪些物品装入背包,可使这些物品的耗费的空间总和不超过背包容量,且价值总和最大。n2. 思路n题目虽然说得有无限多个,但事实上最多装[...
【动态规划】三种背包问题(01背包、完全背包、多重背包)
一、01背包nn问题描述:给定n个物体(它们的重量为:w1,w2,......,wn,价值为:v1,v2,......,vn) 和 一个承受重量为W的背包,问怎么选取这些物体,放在背包中(不超过背包的承重),让所取的子集达到最大价值。nn1、基本实现nn首先,我们很自然想到穷举法,只要给出n个物体的所有组合(子集),分别各个子集的总价值,去掉那些总重量超过背包承重W的子集之后,对剩下的子集中找到总...
二维多重背包问题及基于遗传算法的解决方案
有代码,有详细文档,有毕业论文 非常好的一个毕业设计
多重背包问题 II
题目nn有N种物品和一个容量是V的背包。nn第i种物品最多有si 件,每件体积是vi,价值是wi。nn求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。n输出最大价值。nn输入格式nn第一行两个整数,N,V 用空格隔开,分别表示物品种数和背包容积。nn接下来有N行,每行三个整数vi,wi,si,用空格隔开,分别表示第ii种物品的体积、价值和数量。n...
多维多背包问题Matlab实现
2016年8月25日星期四nT.s.road总结笔记:多维多背包问题Matlab实现n项目源码:https://github.com/Tsroad/KnapsackProblemSeriesnn n作者说明:nWhen running thisprogramme, the author’s PCsetting is:nMicrosoft Windows 7 (SP1) + Matla
完全背包问题+01背包问题+分组背包+多重背包 总结
背包问题都涉及到动态规划,利用dp进行更加优化的计算。n最基本的是01背包问题,题目一般类似:“在一定数目物品内,挑选总重量不超过一定数目的物品,其中每个物品只能选一次,求背包内物品价值的最大值或者最小值”,从名字就可以看出,要么选0个,要么选1个。n如果按照暴力的方法,时间复杂度会爆表,这里采用的是记忆化搜索的方式,加以DP。n首先,选一个二维数组dp,这个数组的含义是从前i个物品中选出总重量不...
背包问题(0-1背包,完全背包,多重背包知识概念详解)
背包问题(0-1背包,完全背包,多重背包知识概念详解)内含实例代码解析,详细讲解了背包的基本概念及简单运用问题
单调队列优化多重背包
多重背包的最原始的状态转移方程:令 c[i] = min(num[i], j / v[i])f[i][j] = max(f[i-1][j-k*v[i]] + k*w[i]) (1 <= k <= c[i]) 这里的 k 是指取第 i 种物品 k 件。如果令 a = j / v[i] , b = j % v[i] 那么 j = a * v[i] + b.这里用 k 表示的意义改变, k 表示
背包问题详解:01背包、完全背包、多重背包
参考链接:nhttp://www.cnblogs.com/fengty90/p/3768845.htmlnhttp://blog.csdn.net/mu399/article/details/7722810nhttp://blog.csdn.net/xiaowei_cqu/article/details/8191808nhttp://blog.csdn.net/insistgogo/article/
背包问题的二进制优化
关于二进制优化这一点,它为什么正确,为什么合理,凭什么可以这样分,至少我是花了很久很久才理解的,先拿一道题来说吧。rnrnHDU 2844 Coinsrn题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2844rn题目:rnrnrnCoinsrnTime Limit: 2000/1000 MS (Java/Others)    Memory Limit
背包问题汇总-01背包、完全背包、多重背包-java
 nnn一、01背包nnnn内容:有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大 nn特点:每个物品只有一件供你选择放还是不放nnn1. 二维解法 nn    设f[i][j]表示前i件物品 总重量不超过j的最大价值 可得出状态转移方程 :nn        f[i][j]=max{f[i-1][j-w[i]]+v[i],f[i-1][j...
背包问题的递归形式解
背包问题是学习算法和数据结构时肯定会接触到的,我老早就了解到这个问题,可直到今天看到《挑战》书上才详细了解这个问题.n该问题的题设和要求如上。n拿到这个问题,最先想到的思路就是利用递归针对每个物品是否放入背包进行两种情况下的搜索。详细的源码和解释如下:
背包问题的方案数(01)
[题见洛谷](https://www.luogu.org/problem/show?pid=1164#sub)n#include<iostream>n#include<cstdio>n#include<cstring>n#include<algorithm>n#include<cmath>n#define LL long longnusing namespace std;nint a[200];nL
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 python最佳入门教程 如何网页制作已有视频