目录前言01背包问题现实应用穷举画图代码前言该问题是“最少钱币数问题”的延伸整个代码结构类似如果不了解可先参考算法.动态规划.最少钱币数问题Java递归_要钱也要自我实现-CSDN博客算法.动态规划.最少钱币数问题Java递归https://blog.csdn.net/weixin_42754896/article/details/123066509完全背包问题在N件物品取出若干件放在容量为W的背包里每种物品的体积为W1W2……WnWi为整数与之相对应的价值为P1,P2……PnPi为整数。求背包能够容纳的最大价值。跟01背包的区别每种东西有无限个现实应用盗墓者 拿了一个背包体积W一定。墓葬中有不同体积的金块价值各不一样。盗墓者当然希望尽可能拿走最大价值的金子。 东西编号 D1 D2 D3 D4 体积W 2 3 4 5 价值V 3 4 5 6 背包体积W8穷举画图假设有两个东西D1 D2每次选择都有两种选择直到包里装不下东西(根据体积来算或者拿不了(根据重量))。 F(W) D1 D2 ---- 第一次选择 D1 D2 D1 D2 ---- 第二次选择 D1 D2 D1 D2 D1 D2 D1 D2 ---- 第三次选择 …… F(8): 装满体积8的最大价值 D1.W: D1东西的体积 D2.V: D2东西的价值 F(W) Max( F(W-D1.W) D1.V,F(W-D2.W)D2.V )代码public class package01 { Test public void test1(){ /** * 体积W 2 3 4 5 * 价值V 3 4 5 6 */ Dong [] dongs new Dong[4]; dongs[3] new Dong(2,3); dongs[2] new Dong(3,4); dongs[1] new Dong(4,5); dongs[0] new Dong(5,6); // 背包体积 int w 8; // 问题求 钱的张数最小 Solution Solution new Solution(); Assert.assertEquals(12, Solution.maxValue01(dongs,w)); } class Solution { public int maxValue01(Dong[] dongs,int w) { if(w 0){ return 0; } int maxValue 0; int tempMaxValue 0; for(int i 0 ; i dongs.length ; i,tempMaxValue 0){ if(dongs[i].w w){ // 背包装不下当前东西的体积直接比背包大装个屁直接忽略 continue; }else if(dongs[i].w w){ /** * 背包装得下东西体积跟背包体积一样大或者小于 * 剩余体积能装最大的价值 当前装的东西的价值 * F(W) Max( F(W-D1.W) D1.V, F(W-D2.W)D2.V ) */ tempMaxValue maxValue01(dongs , w - dongs[i].w) dongs[i].v; } // 如果这种币值的钱张数 比较少就记录 if(tempMaxValue maxValue){ maxValue tempMaxValue; } } return maxValue; } } class Dong{ public int w; public int v; public Dong(){} public Dong(int w,int v){ this.w w; this.v v; } } }end