2023年8月1日发(作者：)

算法设计分析——多背包问题（java）问题描述 多背包问题(MultiplePack)：有N种物品和⼀个容量为V的背包。第i种物品最多有n[i]件可⽤，每件费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。是0-1背包问题的延伸，与0-1背包问题的不同点在于把⼀个背包换成了多个背包，⼤致意思是有⼀堆物品放⼊n个背包中，要使其价值最⼤，应该怎么放。这个问题进⼀步延伸是不考虑n个背包价值最⼤化，⽽是要使得n各背包的价值尽可能相同。详见：（解决⽅案因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表⽰前i种物品恰放⼊⼀个容量为v的背包的最⼤权值，则有状态转移⽅程：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}将其转换为01背包，普通的转换对于数量较多时，则可能会超时，可以转换成⼆进制，对于普通的，就是多了⼀个中间的循环，把j=0~bag[i]，表⽰把第i中背包从取0件枚举到取bag[i]件。核⼼代码public static void multiplePack(int cost,int weight,int amount) { if(cost * amount >= V) { completePack(cost, weight); return; } int k = 1; while(k < amount) { zeroOnePack(k * cost, k * weight); amount -= k; k *= 2; } zeroOnePack(amount * cost, amount * weight);}

public static void completePack(int cost,int weight) { for(int j = cost; j <= V; j++) { f[j] = (f[j], f[j-cost] + weight); }}

public static void zeroOnePack(int cost,int weight) { for(int j = V; j >= cost; j--) { f[j] = (f[j], f[j-cost] + weight); }}全部代码在：输⼊输出⽰例

2023年8月1日发(作者：)

算法设计分析——多背包问题（java）问题描述 多背包问题(MultiplePack)：有N种物品和⼀个容量为V的背包。第i种物品最多有n[i]件可⽤，每件费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。是0-1背包问题的延伸，与0-1背包问题的不同点在于把⼀个背包换成了多个背包，⼤致意思是有⼀堆物品放⼊n个背包中，要使其价值最⼤，应该怎么放。这个问题进⼀步延伸是不考虑n个背包价值最⼤化，⽽是要使得n各背包的价值尽可能相同。详见：（解决⽅案因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表⽰前i种物品恰放⼊⼀个容量为v的背包的最⼤权值，则有状态转移⽅程：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}将其转换为01背包，普通的转换对于数量较多时，则可能会超时，可以转换成⼆进制，对于普通的，就是多了⼀个中间的循环，把j=0~bag[i]，表⽰把第i中背包从取0件枚举到取bag[i]件。核⼼代码public static void multiplePack(int cost,int weight,int amount) { if(cost * amount >= V) { completePack(cost, weight); return; } int k = 1; while(k < amount) { zeroOnePack(k * cost, k * weight); amount -= k; k *= 2; } zeroOnePack(amount * cost, amount * weight);}

public static void completePack(int cost,int weight) { for(int j = cost; j <= V; j++) { f[j] = (f[j], f[j-cost] + weight); }}

public static void zeroOnePack(int cost,int weight) { for(int j = V; j >= cost; j--) { f[j] = (f[j], f[j-cost] + weight); }}全部代码在：输⼊输出⽰例