01背包问题
怎样输出选择的那些物品放入了背包-CSDN论坛
01背包问题
怎样输出选择的那些物品放入了背包
#include&iostream&
using&namespace&
const&int&n=5,C=20;
//int&selected[21][6];
int&main()
int&find(int&s[],int&v[]);
int&s[n+1]=&{0,7,13,6,4,3},v[n+1]=&{0,5,7,3,2,3};
maxValue=find(s,v);
cout&&"maxValue="&&maxValue&&
/*for(int&i=1;i&=n;i++)
&&&&cout&&selected[C][i]&&'&';*/
system("pause");
int&find(int&s[],int&v[])
int&V[n+1][C+1];
for(i=0;i&=n;i++)
V[i][0]=0;
for(j=0;j&=C;j++)
V[0][j]=0;
for(i=1;i&=n;i++)
for(j=0;j&=C;j++)
V[i][j]=V[i-1][j];
&&&&&&&&&&&&if(s[i]&&=&j&&&&V[i-1][j]&&&V[i-1][j-s[i]]+v[i])
&&&&&&&&&&&&{&&
&&&&&V[i][j]=V[i-1][j-s[i]]+v[i];
&&&&&/*if(j==C)
&&&&&&&&selected[j][i]=1;
&&&&&&&&&&&&&&&&&}*/
&&&&&&&&&&&&}
&&&&return&V[n][C];
上面是用动态规划写的程序&最优解已经求出来是13了&但是如果要输出选择了那些物品放入了背包而得出的最优解&那么应该怎么设置标志数组呢&或者用其他的方法能得到呢?
lz仔细看看这个链接，里面讲了如何输出结果和优化问题：
http://blog.csdn.net/Simon_Ghost/archive//1398157.aspx
http://blog.csdn.net/topgun_topgun/archive//1659988.aspx
&楼主有深度，数据安全加密的问题都亲自实现了
这个网上代码很多。优化版会把楼主所说的功能去掉。
呵呵，我们学密码学的时候也讲过这个
回复 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
01背包问题及变种详解
下载积分：100
内容提示：01背包问题及变种详解
文档格式：PDF|
浏览次数：285|
上传日期： 02:43:34|
文档星级：
全文阅读已结束，如果下载本文需要使用
 100 积分
下载此文档
该用户还上传了这些文档
01背包问题及变种详解
官方公共微信196165人阅读
01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。
01背包的状态转换方程&f[i,j] = Max{ f[i-1,j-Wi]+Pi( j &= Wi ), &f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值。
决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？
题目描述：
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。
首先要明确这张表是至底向上，从左到右生成的。
为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。
对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。
同理，c2=0，b2=3,a2=6。
对于承重为8的背包，a8=15,是怎么得出的呢？
根据01背包的状态转换方程，需要考察两个值，
一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；
&f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
f[i-1,j-Wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6
由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包
以下是actionscript3 的代码
public function get01PackageAnswer(bagItems:Array,bagSize:int):Array
var bagMatrix:Array=[];
var item:PackageI
for(i=0;i&bagItems.i++)
bagMatrix[i] = [0];
for(i=1;i&=bagSi++)
for(var j:int=0;j&bagItems.j++)
item = bagItems[j] as PackageI
if(item.weight & i)
//i背包转不下item
bagMatrix[j][i] = 0;
bagMatrix[j][i]=bagMatrix[j-1][i];
//将item装入背包后的价值总和
var itemInBag:
bagMatrix[j][i] = item.
itemInBag = bagMatrix[j-1][i-item.weight]+item.
bagMatrix[j][i] = (bagMatrix[j-1][i] & itemInBag ? bagMatrix[j-1][i] : itemInBag)
//find answer
var answers:Array=[];
var curSize:int = bagS
for(i=bagItems.length-1;i&=0;i--)
item = bagItems[i] as PackageI
if(curSize==0)
if(i==0 && curSize & 0)
answers.push(item.name);
if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value)
answers.push(item.name);
curSize -= item.
PackageItem类
public class PackageItem
public var name:S
public var weight:
public var value:
public function PackageItem(name:String,weight:int,value:int)
this.name =
this.weight =
this.value =
var nameArr:Array=['a','b','c','d','e'];
var weightArr:Array=[2,2,6,5,4];
var valueArr:Array=[6,3,5,4,6];
var bagItems:Array=[];
for(var i:int=0;i&nameArr.i++)
var bagItem:PackageItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]);
bagItems[i]=bagI
var arr:Array = ac.get01PackageAnswer(bagItems,10);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：474355次
积分：3606
积分：3606
排名：第9322名
原创：56篇
转载：15篇
评论：177条
(2)(1)(1)(6)(4)(4)(3)(1)(1)(4)(2)(2)(1)(1)(2)(5)(4)(1)(1)(1)(1)(1)(3)(7)(1)(1)(1)(1)(2)(5)(1)(1)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'一、问题描述：有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
二、总体思路：根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现；
三、动态规划的原理及过程：
eg：number＝4，capacity＝8
动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
a)&把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积（重量）；
b)&建立模型，即求max(V1X1+V2X2+…+VnXn)；
c)&约束条件，W1X1+W2X2+…+WnXn&capacity；
d)&定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；
e) 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理，采用反证法证明：
假设(X1，X2，…，Xn)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解，
假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1&& (V2X2+V3X3+…+VnXn)+V1X1；
而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)，则有(V2Y2+V3Y3+…+VnYn)+V1X1&&&(V1X1+V2X2+…+VnXn)；
该式子说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理；
f)&寻找递推关系式，面对当前商品有两种可能性：
第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；
由此可以得出递推关系式：
1) j&w(i) &&&&&V(i,j)=V(i-1,j)
2) j&=w(i) &&&&V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝
g)&填表，首先初始化边界条件，V(0,j)=V(i,0)=0；
h)&然后一行一行的填表，
1)&如，i=1，j=1，w(1)=2，v(1)=3，有j&w(1)，故V(1,1)=V(1-1,1)=0；
2)&又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；
3)&如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j&w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10；所以填完表如下图：
1 void FindMax()//动态规划
for(i=<span style="color: #;i&=i++)
for(j=<span style="color: #;j&=j++)
if(j&w[i])//包装不进
<span style="color: #
<span style="color: #
V[i][j]=V[i-<span style="color: #][j];
<span style="color: #
<span style="color: #
else//能装
<span style="color: #
<span style="color: #
if(V[i-<span style="color: #][j]&V[i-<span style="color: #][j-w[i]]+v[i])//不装价值大
<span style="color: #
<span style="color: #
V[i][j]=V[i-<span style="color: #][j];
<span style="color: #
<span style="color: #
else//前i-1个物品的最优解与第i个物品的价值之和更大
<span style="color: #
<span style="color: #
V[i][j]=V[i-<span style="color: #][j-w[i]]+v[i];
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: # }
i)&表格填完，最优解即是V(number,capacity)=V(4,8)=10，但还不知道解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：
1)&V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；
2)&V(i,j)=V(i-1,j-w(i))+v(i)实时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
3)&一直遍历到i＝0结束为止，所有解的组成都会找到。
j)&如上例子，
1)&最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；
2)&有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；
3)&而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；
4)&有V(1,0)=V(0,0)=0，所以第1件商品没被选择；
k)&到此，01背包问题已经解决，利用动态规划解决此问题的效率即是填写此张表的效率，所以动态规划的时间效率为O(number*capacity)=O(n*c)，由于用到二维数组存储子问题的解，所以动态规划的空间效率为O(n*c)；
1 void FindWhat(int i,int j)//寻找解的组成方式
if(i&=<span style="color: #)
if(V[i][j]==V[i-<span style="color: #][j])//相等说明没装
item[i]=<span style="color: #;//全局变量，标记未被选中
FindWhat(i-<span style="color: #,j);
<span style="color: #
else if( j-w[i]&=<span style="color: # && V[i][j]==V[i-<span style="color: #][j-w[i]]+v[i] )
<span style="color: #
<span style="color: #
item[i]=<span style="color: #;//标记已被选中
<span style="color: #
FindWhat(i-<span style="color: #,j-w[i]);//回到装包之前的位置
<span style="color: #
<span style="color: #
<span style="color: # }
3、空间优化
l)&空间优化，每一次V(i)(j)改变的值只与V(i-1)(x) {x:1...j}有关，V(i-1)(x)是前一次i循环保存下来的值；
因此，可以将V缩减成一维数组，从而达到优化空间的目的，状态转移方程转换为&B(j)= max{B(j), B(j-w(i))+v(i)}；
并且，状态转移方程，每一次推导V(i)(j)是通过V(i-1)(j-w(i))来推导的，所以一维数组中j的扫描顺序应该从大到小(capacity到0)，否者前一次循环保存下来的值将会被修改，从而造成错误。
m)&同样以上述例子中i=3时来说明，有:
1)&i=3，j=8，w(3)=4，v(3)=5，有j&w(3)，则B(8)=max｛B(8)，B(8-w(3))+v(3)｝=max｛B(8)，B(4)+5｝=max｛7，4+5｝=9；
2)&j- -即j=7，有j&w(3)，则B(7)=max｛B(7)，B(7-w(3))+v(3)｝=max｛B(7)，B(3)+5｝=max｛7，4+5｝=9；
3)&j- -即j=6，有j&w(3)，则B(6)=max｛B(6)，B(6-w(3))+v(3)｝=max｛B(6)，B(2)+5｝=max｛7，3+5｝=8；
4)&j- -即j=5，有j&w(3)，则B(5)=max｛B(5)，B(5-w(3))+v(3)｝=max｛B(5)，B(1)+5｝=max｛7，0+5｝=7；
5)&j- -即j=4，有j＝w(3)，则B(4)=max｛B(4)，B(4-w(3))+v(3)｝=max｛B(4)，B(0)+5｝=max｛4，0+5｝=5；
6)&j- -即j=3，有j&w(3)，继续访问数组会出现越界，所以本轮操作停止，B(0)到B(3)的值保留上轮循环（i=2时）的值不变，进入下一轮循环i++；
如果j不逆序而采用正序j=0...capacity，如上图所示，当j=8时应该有B(8)=B(8-w(3))+v(3)=B(4)+5，然而此时的B(4)已经在j=4的时候被修改过了，原来的B(4)=4，现在B(4)=5，所以计算得出B(8)=5+5=10，显然这于正确答案不符合；所以该一维数组后面的值需要前面的值进行运算再改动，如果正序便利，则前面的值将有可能被修改掉从而造成后面数据的错误；相反如果逆序遍历，先修改后面的数据再修改前面的数据，此种情况就不会出错了；
1 void FindMaxBetter()//优化空间后的动态规划
for(i=<span style="color: #;i&=i++)
for(j=j&=<span style="color: #;j--)
if(B[j]&=B[j-w[i]]+v[i] && j-w[i]&=<span style="color: # )//二维变一维
<span style="color: #
B[j]=B[j-w[i]]+v[i];
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: # }
n)&然而不足的是，虽然优化了动态规划的空间，但是该方法不能找到最优解的解组成，因为动态规划寻早解组成一定得在确定了最优解的前提下再往回找解的构成，而优化后的动态规划只用了一维数组，之前的数据已经被覆盖掉，所以没办法寻找，所以两种方法各有其优点。
四、蛮力法检验：
1) 蛮力法是解决01背包问题最简单最容易的方法，但是效率很低
2) (X1，X2，…，Xn)其中Xi＝0或1表示第i件商品选或不选，共有n(n-1)/2种可能；
3) 最简单的方式就是把所有拿商品的方式都列出来，最后再做判断此方法是否满足装包条件，并且通过比较和记录找出最优解和解组成（如果满足则记录此时的价值和装的方式，当下一次的装法优于这次，则更新记录，如此下去到最后便会找到最优解，同时解组成也找到）；
4) n件商品，共有n(n-1)/2种可能，故蛮力法的效率是指数级别的，可见效率很低;
5) 蛮力法效率低不建议采取，但可以用于检验小规模的动态规划解背包问题的正确性和可行性，如下图输出可见，解01背包问题用动态规划是可行的：
五、总结：
对于01背包问题，用蛮力法与用动态规划解决得到的最优解和解组成是一致的，所以动态规划解决此类问题是可行的。动态规划效率为线性，蛮力法效率为指数型，结合以上内容和理论知识可以得出，解决此问题用动态规划比用蛮力法适合得多。对于动态规划不足的是空间开销大，数据的存储得用到二维数组；好的是，当前问题的解只与上一层的子问题的解相关，所以，可以把动态规划的空间进行优化，使得空间效率从O(n*c)转化为O(c)，遗憾的是，虽然优化了空间，但优化后只能求出最优解，解组成的探索方式在该方法运行的时候已经被破坏掉；总之动态规划和优化后的动态规划各有优缺点，可以根据实际问题的需求选择不同的方式。
六、引申：
动态规划可以解决哪些类型的问题？
待解决的原问题较难，但此问题可以被不断拆分成一个个小问题，而小问题的解是非常容易获得的；如果单单只是利用递归的方法来解决原问题，那么采用的是分治法的思想，动态规划具有记忆性，将子问题的解都记录下来，以免在递归的过程中重复计算，从而减少了计算量。
阅读(...) 评论()15118人阅读
动态规划（46）
有n 种不同的物品，每个物品有两个属性，size 体积，value 价值，现在给一个容量为 w 的背包，问最多可带走多少价值的物品。
int f[w+1];
//f[x] 表示背包容量为x 时的最大价值
for (int i=0; i&n; i++)
for (int j=w; j&=size[i]; j--)
f[j] = max(f[j], f[j-size[i]]+value[i]);
如果物品不计件数，就是每个物品不只一件的话，稍微改下即可 &
for (int i=0; i&n; i++)
for (int j=size[i]; j&=w; j++)
f[j] = max(f[j], f[j-size[i]]+value[i]);
& & & &&f[w] 即为所求 &
&&&&&&& 初始化分两种情况：
&&&&&&& 1、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF; &
&&&&&&& 2、如果不需要正好装满 f[0~v] = 0; &
& & & & 举例：
V=10，N=3，c[]={3,4,5}, w={4,5,6}
（1）背包不一定装满
& & & 计算顺序是：从右往左，自上而下：因为每个物品只能放一次，前面的体积小的会影响体积大的
（2）背包刚好装满 & &
& & & 计算顺序是：从右往左，自上而下。注意初始值，其中-inf表示负无穷
完全背包：
V=10，N=3，c[]={3,4,5}, w={4,5,6}
（1）背包不一定装满
计算顺序是：从左往右，自上而下： &每个物品可以放多次，前面的会影响后面的
（2）背包刚好装满
计算顺序是：从左往右，自上而下。注意初始值，其中-inf表示负无穷
多重背包： &
& & & & &多重背包问题要求很简单，就是每件物品给出确定的件数，求可得到的最大价值 &
& & & & &多重背包转换成 01 背包问题就是多了个初始化，把它的件数C 用二进制分解成若干个件数的集合，这里面数字可以组合成任意小于等于C的件数，而且不会重复，之所以叫二进制分解，是因为这样分解可以用数字的二进制形式来解释
& & & &比如：7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以组合成任意小于等于7 的数，而且每种组合都会得到不同的数
& & & &15 = 1111 可分解成 &
四个数字 &
&&&&&&& 如果13 = 1101 则分解为 00 0110 前三个数字可以组合成 &7以内任意一个数，即1、2、4可以组合为1——7内所有的数，加上
0110 = 6 可以组合成任意一个大于6 小于等于13的数，比如12，可以让前面贡献6且后面也贡献6就行了。虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种思想去把多件物品转换为，多种一件物品，就可用01
背包求解了。 &
&&&& & 看代码： &
//输入有多少种物品
//每种物品有多少件
//每种物品的价值
//每种物品的尺寸
int count = 0; //分解后可得到多少种物品
int value[MAX]; //用来保存分解后的物品价值
int size[MAX];
//用来保存分解后物品体积
scanf(&%d&, &n);
//先输入有多少种物品，接下来对每种物品进行分解
while (n--)
//接下来输入n中这个物品
scanf(&%d%d%d&, &c, &s, &v);
//输入每种物品的数目和价值
for (int k=1; k&=c; k&&=1)
//&&右移 相当于乘二
value[count] = k*v;
size[count++] = k*s;
if (c & 0)
value[count] = c*v;
size[count++] = c*s;
定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1&0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。
证明如下：
（1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；
（2）如果正整数t&= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.
（3）如果t&=2^k,设s=n-2^k+1，则t-s&=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。
（证毕！）
&&&&&&& 现在用count 代替 n 就和01 背包问题完全一样了&&
杭电2191题解：此为多重背包用01和完全背包：
#include&stdio.h&
#include&string.h&
int dp[102];
int p[102],h[102],c[102];
void comback(int v,int w)//经费，重量。完全背包；
for(int i=v; i&=n; i++)
if(dp[i]&dp[i-v]+w)
dp[i]=dp[i-v]+w;
void oneback(int v,int w)//经费，重量；01背包；
for(int i=n; i&=v; i--)
if(dp[i]&dp[i-v]+w)
dp[i]=dp[i-v]+w;
int main()
int ncase,i,j,k;
scanf(&%d&,&ncase);
while(ncase--)
memset(dp,0,sizeof(dp));
scanf(&%d%d&,&n,&m);//经费，种类；
for(i=1; i&=m; i++)
scanf(&%d%d%d&,&p[i],&h[i],&c[i]);//价值，重量，数量;
if(p[i]*c[i]&=n) comback(p[i],h[i]);
for(j=1; j&c[i]; j&&1)
oneback(j*p[i],j*h[i]);
c[i]=c[i]-j;
oneback(p[i]*c[i],h[i]*c[i]);
printf(&%d\n&,dp[n]);
只是用01背包，用二进制优化：
#include &iostream&
int main()
int nCase,Limit,nKind,i,j,k,
v[111],w[111],c[111],dp[111];
//v[]存价值，w[]存尺寸，c[]存件数
//在本题中，价值是米的重量，尺寸是米的价格
int count,Value[1111],size[1111];
//count存储分解完后的物品总数
//Value存储分解完后每件物品的价值
//size存储分解完后每件物品的尺寸
while(nCase--)
cin&&Limit&&nK
for(i=0; i&nK i++)
cin&&w[i]&&v[i]&&c[i];
//对该种类的c[i]件物品进行二进制分解
for(j=1; j&=c[i]; j&&=1)
//&&左移1位，相当于乘2
Value[count]=j*v[i];
size[count++]=j*w[i];
if(c[i]&0)
Value[count]=c[i]*v[i];
size[count++]=c[i]*w[i];
//经过上面对每一种物品的分解，
//现在Value[]存的就是分解后的物品价值
//size[]存的就是分解后的物品尺寸
//count就相当于原来的n
//下面就直接用01背包算法来解
memset(dp,0,sizeof(dp));
for(i=0; i& i++)
for(j=L j&=size[i]; j--)
if(dp[j]&dp[j-size[i]]+Value[i])
dp[j]=dp[j-size[i]]+Value[i];
cout&&dp[Limit]&&
未优化的：
#include&iostream&
#include&cstdio&
#include&cstring&
int Value[105];
int Cost[105];
int Bag[105];
int dp[105];
int main()
int C,m,n;
scanf(&%d&,&C);
while(C--)
scanf(&%d%d&,&n,&m);
for(int i = 1; i &= i++)
scanf(&%d%d%d&,&Cost[i],&Value[i],&Bag[i]);
memset(dp,0,sizeof(dp));
for(int i=1; i&= i++)
for(int j=1; j&=Bag[i]; j++)
for(int k=n; k&=Cost[i]; k--)
dp[k]=max(dp[k], dp[k-Cost[i]]+Value[i]);
printf(&%d\n&,dp[n]);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：551354次
积分：8699
积分：8699
排名：第2249名
原创：319篇
评论：107条
(1)(2)(3)(3)(1)(3)(1)(1)(2)(12)(10)(17)(12)(35)(20)(1)(4)(31)(14)(16)(10)(1)(7)(6)(3)(9)(25)(5)(15)(30)(7)(1)(12)
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'
