👨🎓作者简介：一位喜欢写作，计科专业大二菜鸟
🏡个人主页：starry陆离
🕒首发日期：2022年5月17日星期二
🌌上期文章：【Android】网络编程之OKHTTP与Retrofit框架
📚订阅专栏：Android基础入门如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
@TOC
笔者的话
这篇文章比较粗糙，因为是面向掌握了01背包问题的读者，如若没有此基础请看上期文章；对于有01背包问题基础的读者肯定一看就懂
1. 问题描述
有n个物品，第i个物品的重量与价值分别为w[i]与v[i]且第i种物品最多有s[i] 件。背包容量为c，试问在每个物品不超过其上限的件数（物品必须保持完整）的情况下，如何让背包装入的物品具有更大的价值总和。
与01背包问题不同，物品的数量不再是一个，而是多个，那么物品的选择也不再是选与不选，而是选0个，选1个，选2个。。。选s[i]个；然后求出这些组合中的价值总和最大的组合的值即为解
01背包的通式：
2. dp方程
有了01背包的基础，构造多重背包的递推通式应该很简单了（自顶向下构造多重背包）
我们可以对比01背包的通式（自顶向下构造01背包）：
3. 核心代码
for(inti=1;i<=n;++i) { for(intj=1;j<=c;++j) { for(intk=0;k<=s[i]&&k*w[i]<=j;++k) { dp[i][j]=Math.max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i]); } } }
4. 小试牛刀
原题链接：https://acm.hnucm.edu.cn/JudgeOnline/
题目描述
在某网络游戏中提供了一个道具库，在道具库中每种道具均有若干件（数量已知），游戏玩家购买一件道具将获得一定的魅力值。已知每种道具的价格和魅力值，请编写一个程序，在总价格不超过某个上限的情况下使得所购道具的魅力值之和达到最大。
输入
每组测试数据的输入有n+1行，n表示道具的种类。（n<=100，p<=10000）第1行包含两个正整数，分别表示道具种类数n和总价值的上限p，两个数字之间用空格隔开。第2行到第n+1行分别对应于第1种道具到第n种道具的信息，每1行包含三个正整数，两个数字之间用空格隔开，三个正整数分别表示某一种道具的数量、单个道具的价格和魅力值。
输出
每组测试数据的输出只有一行，即道具魅力值的最大和。
样例输入
310
223
1510
2412
样例输出
27
importjava.util.Scanner; publicclassMain { publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); intn,c; int[] s,w,v; int[][] dp; while(scanner.hasNext()) { n=scanner.nextInt(); c=scanner.nextInt(); s=newint[n+1]; w=newint[n+1]; v=newint[n+1]; dp=newint[n+1][c+1]; for(inti=1;i<=n;++i) { s[i]=scanner.nextInt(); w[i]=scanner.nextInt(); v[i]=scanner.nextInt(); } for(inti=1;i<=n;++i) { for(intj=1;j<=c;++j) { for(intk=0;k<=s[i]&&k*w[i]<=j;++k) { dp[i][j]=Math.max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i]); } } } System.out.println(dp[n][c]); } } }
5. 扩展：空间压缩
与01背包问题类似，注意数值覆盖问题即可
//压缩空间for(inti=1;i<=n;++i) { for(intj=c;j>=1;--j) { for(intk=0;k<=s[i]&&k*w[i]<=j;++k) { m[j]=Math.max(m[j], m[j-k*w[i]]+k*v[i]); } } }
