威海住房和城乡建设厅网站,photoshop制作网站海报,福建网站制作,老网站做成适合手机端的网站怎么做一、前言
最近打算出一个背包问题的专栏#xff0c;详细介绍一下常见的几种不同类型的背包问题及其解题思路和方法#xff0c;欢迎各位留言探讨。
二、什么是背包问题#xff1f;
背包问题是动态规划中的一个分支#xff0c;其目标是在给定的一组物品中选择一些物品放入…一、前言
最近打算出一个背包问题的专栏详细介绍一下常见的几种不同类型的背包问题及其解题思路和方法欢迎各位留言探讨。
二、什么是背包问题
背包问题是动态规划中的一个分支其目标是在给定的一组物品中选择一些物品放入背包使得在满足背包容量限制的情况下所选物品的总价值最大化或总重量最小化。背包问题大致可以分为9类本章讲解的是01背包问题。
三、01背包
3.1 问题描述
有n个物品和一个容量为capacity的背包每种物品只有一件他们的体积分别为weights[i](0in)价值分别为values[i](0in)求将哪些物品装入背包可使价值总和最大
3.2 解体思路
3.2.1 确定状态变量函数
最大价值是物品数量i与背包容量j的函数设dp[i][j]表示从前i件物品中进行选择放入容量为j的背包所能获得的最大价值
3.2.2 确定状态转移方程递推关系
对于第i个物品(第1个物品为weights[0]第i个物品为weights[i-1])的选择情况如下
1.如果当前背包剩余容量jweights[i-1]则无法将该物品装入背包此时最大价值与从前i-1个物品选择放入容量为j的背包所能获得的最大价值相同dp[i][j] dp[i-1][j]2.如果当前背包剩余容量jweights[i-1]则能放入第i件物品但是需要判断放入该物品与不放入时哪种情况所能取到的价值最大。 如果第i件物品不放入背包dp[i][j] dp[i-1][j]如果第i件物品放入背包背包剩余容量为j-weights[i-1]要使总价值最大相当于从前i-1个物品中进行选择放入容量为j-weights[i]的背包的最大价值再加上第i件物品的价值values[i-1]dp[i][j] dp[i-1][j-weights[i-1]] values[i-1]3.2.3 确定边界条件
当背包容量为0时无法放入任何物品到背包中总价值为0即dp[i][0]0 (0in)当不放入任何物品到背包中时总价值也为0即dp[0][j]0(0jn)
3.2.4 代码示例
/*** 背包问题-背包9讲*/
public class KnapsackQuestion {/*** 01背包** param weights 存储n件物品重量的数组weights[i-1]表示第i件物品的重量(下标从0开始)* param values 存储n件物品价值的数组values[i-1]表示第i件物品的价值* param capacity 背包的容量* return 从n件物品中进行选择放入容量为capacity的背包中所能取得的最大价值*/public int knapsack01(int[] weights, int[] values, int capacity) {// dp[i][j]表示从前i件物品中选择放入容量为j的背包的最大价值int n weights.length;int[][] dp new int[n 1][capacity 1];for (int i 1; i n; i) {for (int j 1; j capacity; j) {if (j weights[i - 1]) {dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]);} else {dp[i][j] dp[i - 1][j];}}}return dp[n][capacity];}
