一个企业网站做几个关键词,wordpress在媒体库里无法上传图片,邯郸哪个公司做网站好,网站采集注意【动态规划】0-1背包问题
题目:现在有四个物品#xff0c;背包总容量为8#xff0c;背包最多能装入价值为多少的物品? 我的图解
表格a【i】【j】表示的是容量为j的背包装入前i个物品的最大价值。
拿a【1】【1】来说#xff0c;它的值就是背包容量为1#xff0c;只考虑…【动态规划】0-1背包问题
题目:现在有四个物品背包总容量为8背包最多能装入价值为多少的物品? 我的图解
表格a【i】【j】表示的是容量为j的背包装入前i个物品的最大价值。
拿a【1】【1】来说它的值就是背包容量为1只考虑编号01的物品时背包所能装入的最大价值
然后既然是动态规划那就一定有初值也就是a【0】【j】 0; a【i】【0】 0;即第一行和第一列都为0 然后根据初值来推后面的值
首先要判断本行所对应的物品是否能装入背包
拿a【1】【1】来说首先要判断若只考虑编号为1的物品它是否可以装入背包此时的背包容量为1而编号为1的物品的体积为2故它无法装入背包那么a【1】【1】的值和背包容量为1只考虑编号为0的物品时背包所能装入的最大价值(即a【0】【1】)是相等的
若能装入背包那么有两种选择:
(1)装入本行物品即先装入本行的物品然后剩下背包容量装其他价值之和最大的物品
(2)不装本行物品即背包容量都用来装除了本行物品之外的其他物品(即本行前面几行的物品) 然后比较(1)(2)选择较大者 拿a【2】【4】来说此时的背包容量为4,编号为2的物品的体积为3故2号物品能装入背包然后两种选择 (1)装入2号物品此时背包剩余容量为1此时只剩下两个物品那就是编号为0和1的物品查表得a【1】【1】0
故此时的最大价值为a【1】【1】加上2号物品的价值也就是4
(2)不装2号物品即背包容量都用来装除了本行物品之外的其他物品(即本行前面几行的物品) 由于不装入2号物品此时的最大价值和只考虑编号为01物品背包容量为4的情况的最大价值(即a【1】【4】)是相等的 也就是3
故选择(1)(2)中较大者a【2】【4】4;
依次类推下去。
解法归纳:
一、如果装不下当前物品那么前n个物品的最佳组合和前n-1个物品的最佳组是一 样的。
二、如果装得下当前物品。
假设1:装当前物品在给当前物品预留了相应空间的情况下前n-1 个物品的最佳组 合加上当前物品的价值就是总价值。
假设2:不装当前物品那么前n个物品的最佳组合和前n-1个物品的最佳组合是一样 的。
选取假设1和假设2中较大的价值为当前最佳组合的价值。 代码实现
package eunm.Try;//0-1背包问题
public class BB {public static void main(String[] args) {// TODO 自动生成的方法存根int volume[] {2, 3, 4, 5};int value[] {3, 4, 5, 6};int maxvolume 9;System.out.println(knapsack(volume, value, maxvolume));}public static int knapsack(int[] volume, int[] value, int maxvolume) {int n volume.length;//最大价值数组为maxvalue[N1][maxvolume1]因为我们要从0开始保存int[][] maxvalue new int[n 1][maxvolume 1];//体积和物品为0时价值为0for (int j 0; j maxvolume 1; j) {maxvalue[0][j] 0;}for (int i 0; i n 1; i) {maxvalue[i][0] 0;}//i只拿前i件物品这里的i因为取了0所以对应到weight和value里面都是i-1号位置//j假设能取的总体积为j//n是物品件数for (int i 1; i n; i) {for (int j 1; j maxvolume; j) {//当前最大价值等于放上一件的最大价值maxvalue[i][j] maxvalue[i - 1][j];//如果当前件的体积小于总体积可以放进去或者拿出别的东西再放进去if (volume[i - 1] j) {/*比较不放这个物品的价值和这个物品的价值value[i - 1] 加上 当前能放的总体积减去当前物品体积j - volume[i - 1]时取前i-1个物品时的对应体积时候的最高价值maxvalue[i - 1][j - volume[i - 1]]的大小*/if (value[i - 1] maxvalue[i - 1][j - volume[i - 1]] maxvalue[i - 1][j]) {maxvalue[i][j] value[i - 1] maxvalue[i - 1][j - volume[i - 1]];}}}}return maxvalue[n][maxvolume];}}这里比较关键。
//如果当前件的体积小于总体积可以放进去或者拿出别的东西再放进去if (volume[i - 1] j) {/*比较不放这个物品的价值和这个物品的价值value[i - 1] 加上 当前能放的总体积减去当前物品体积j - volume[i - 1]时取前i-1个物品时的对应体积时候的最高价值maxvalue[i - 1][j - volume[i - 1]]的大小*/if (value[i - 1] maxvalue[i - 1][j - volume[i - 1]] maxvalue[i - 1][j]) {maxvalue[i][j] value[i - 1] maxvalue[i - 1][j - volume[i - 1]];}}背包问题回溯在使得背包内总价值最大的情况下背包内装了哪些物品? 这里我暂时不想研究了呜呜脑阔疼。 再来一个今天做的题目小明是一个大胖子为了让体重达到正常水平他的计划是:减掉n千克体重,分多周完成(至少是2周)每周都减重正整数千克。为了激励自己他决定每周减掉的体重都必须比上周减掉的体重多。假设他上周减重0千克他从这周开始执行计划请问可以设计出多少种方案?
套一下上面的模板就行。
package Excepect;import java.util.Scanner;public class AAAA {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();long[][] dp new long[n][n 1];dp[0][0] 1;for (int i 1; i n; i) {//i表示接收体重后体重变化dp[i][0] 1;//第一周开始减最少从1开始for (int j 1; j n; j) {//j表示能减的总体重//当前方案上一体重的方案dp[i][j] dp[i - 1][j];//如果当前体重能减的总体重if (i j) {//最多总方案现有方案能减的总体重-当前体重时取前i-1对应体重的最多总方案dp[i][j] dp[i][j] dp[i - 1][j - i];}}}System.out.println(dp[n - 1][n]);scan.close();}
}突然发现学算法真的很费脑子。。。。。。最近两天家里面在干活我不仅时刻被叫去帮忙干活还要去帮忙做午饭没办法农村家庭里的孩子就是这么命苦呜呜呜所以就没办法专注下来学习断断续续的。
不过总结确实是一件好事不总结的话我可能都学不懂什么。前天晚上弄的那个个人博客吧就如同我朋友说的一样我像极了瞎猫碰见死耗子到处乱碰看看碰到了没。。。 然后一直搞到深夜十二点半才在我的博客主页看到了我写的文章。目前还没成功还没把博客部署到服务器上好像就是差这一步来着。等我搞好了我会写一篇技术文的嘿嘿嘿。
本文由mdnice多平台发布
