定义from百度百科
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
2022-5-30-416-分割等和子集
看答案写出的dp
class Solution {public boolean canPartition(int[] nums) {int sum = 0;int max=0;HashSet<Integer> has = new HashSet<Integer>();for(int i =0;i<nums.length;i++){sum+=nums[i];max = Math.max(max,nums[i]);}int mid = sum/2;int len =nums.length;if(len<2||sum%2!=0||max>mid)return false;//剪枝boolean[][] dp = new boolean[len][mid+1];//有i和j，在i个数里选择和为j的情况dp[0][nums[0]]=true;//边界条件，dp[0][nums[0]]可达for(int i =0;i<dp.length;i++){ if(nums[i]==mid)return true;dp[i][0]=true;for(int j =0;j<dp[0].length;j++){if(i>=1){ if(dp[i-1][j]){dp[i][j]=true;}if(j-nums[i]>=0&&dp[i-1][j-nums[i]])dp[i][j]=true; }}}return dp[len-1][mid];}}
之前的思路：动态规划当然是要寻找最优子结构、怎么迭代到现在的状态呢？直接排序贪心不太行，如何通过记住状态减少重复计算呢？不会不会摆烂了。
真实思路：使用二维数组存储“所有”的计算结果，因为最大情况是可以被考虑的。于是用dp[i]表示前i个数中存储的结果，j表示和是多少。
那么有两个边界状态-自己想想，和转移方程-每个结果要么是上一个j直接有，不选这个数可以”继承“过来，要么是上一个j减去这个nums[i]有，最后返回dp[len-1][mid]就好，注意如果i是下标j是数的话，i要为len但j要为mid+1，防止越界。
本题的知识点包括：
知识点：动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题。在青蛙跳阶问题中：
- f(n-1)和f(n-2) 称为 f(n) 的最优子结构（在这里就是取不取本数）
- f(n)= f（n-1）+f（n-2）就称为状态转移方程（其实和子结构密切相关，包含了推导过程，本题中就是暴力存储）
- f(1) = 1, f(2) = 2 就是边界啦(边界条件)
- 比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。（会被计算多次的问题能否通过一次存储解决？）
有带备忘录的自顶向下和自底向上两种。
- 动态规划的典型案例，用于思考和对比：青蛙跳台阶、最长递增子序列（最长=次长+1）
-
1D
class Solution { public boolean canPartition(int[] nums) { if (nums == null || nums.length == 0) return false; int sum = 0; for (int num : nums) { sum += num; } if (sum % 2 != 0) return false; // 回溯也是target！ int target = sum/2; boolean[] visited = new boolean[target + 1]; return backtracking(nums, 0, target, visited); } private boolean backtracking(int[] nums, int startIndex, int target, boolean[] visited) { // 满足条件即可返回boolean if (target == 0) return true; // 深度不定，挑元素直到和满足要求 for (int i = startIndex; i < nums.length; i++) { // 宽度是数组长度，无序startIndex，不可重复取i+1 target -= nums[i]; // 关键！ if (target < 0 || visited[target]) { // 如果小于0说明这个数不合适，直接回溯跳过 target += nums[i]; continue; } visited[target] = true; // 没有visited，当出现一堆相同数时会超时 if (backtracking(nums, i + 1, target, visited)) return true; target += nums[i]; }//倒着回溯，一路往上走，省去了第一个二维空间也就是i个数 return false; } }2022-5-31 474 1和0
自己的代码
思路：首先创建【三维】数组【本来想二维回溯，但是需要保存当范围为i时的前几个，不然会混，导致前导信息的丢失，导致多次反复加】
之后进入迭代，首先进行继承，但这里不可以直接继承，怕会把后面改的置0(也许可以改成减号)
其次对每个i和j进行迭代，看时选之前的继承还是前一个最优子状态+1
最后在最大范围里找，要注意最大的二号下标不一定最大
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][][] dp = new int[m+1][n+1][strs.length+1];
int k = 1;
for(String str:strs)
{
int num1 = count(str,'1');
int num0 = count(str,'0');
if(num0<dp.length&&num1<dp[0].length)dp[num0][num1][k]=Math.max(dp[num0][num1][k-1],1);
for(int i=0;i<dp.length;i++)
{
for(int j = 0;j<dp[0].length;j++)
{
if(k>1){dp[i][j][k]=Math.max(dp[i][j][k],dp[i][j][k-1]);//边界条件
}//放在外面！！,以及这个会把之前迭代的冲掉
if(i+num0<dp.length&&j+num1<dp[0].length)
{
if(dp[i][j][k-1]!=0)//会有多加的情况
{
dp[i+num0][j+num1][k]=Math.max(dp[i][j][k-1]+1,dp[i+num0][j+num1][k-1]);
//迭代方程
}
//优选最大值
//淘汰掉的去哪了
}
}
}
k++;
}
int max =0;
for(int i=dp.length-1;i>=0;i--)
{
for(int j = dp[0].length-1;j>=0;j--)
{
if(dp[i][j][strs.length]!=0)
{
max=Math.max(max,dp[i][j][strs.length]);
}
}
}
return max;
}
public int count(String s,char c){
char[] ch=s.toCharArray();
int i = 0;
for(char cs:ch)
{
if(cs==c)i+=1;
}
return i;
}
}
别人的代码
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int dp[][] = new int[m+1][n+1];//边界条件
for (int i = 1; i <= len; i++) {
int zero = 0, one = 0;
String str = strs[i-1];
for (int c = 0; c < str.length(); c++){
if (str.charAt(c) == '0') zero ++;
else one ++;
}
//数0和1
for (int j = m; j >= zero; j--) {
for (int k = n; k >= one; k--) {//重要，倒着来
dp[j][k] = Math.max(dp[j][k], dp[j-zero][k-one]+1);
//转移方程
}
}
}
return dp[m][n];
}
}
2022-6-1 494 目标和
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int x:nums)
{
sum+=x;
}
if(sum<target||-sum>target)return 0;
int[][] dp=new int[nums.length+1][2*sum+1];
dp[0][sum]=1;
for(int k =1;k<nums.length+1;k++)
{
for(int i =0;i<2*sum+1;i++)
{
if(dp[k-1][i]!=0)
{
dp[k][i+nums[k-1]]+=dp[k-1][i];
dp[k][i-nums[k-1]]+=dp[k-1][i];
}
}
}
return dp[nums.length][sum+target];
}
}
这是典型的动态规划，边界是数为0的时候纳入背包的物品数量，最优子状态是从上一个减去这一个或是上一个加上这一个。本题注意事项包括：
- 如何处理+-sum和0之间的关系，设计多大的数组，要不要加一（在这里是两个都要，主要是看参数含义）
- dp的长度-可能出现的情况值和可能出现的情况数，dp的内容-要转移的状态。
2022-6-2 1049 最后一块石头的重量
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int stone:stones)
{
sum+=stone;
}
boolean[][] dp = new boolean[stones.length+1][sum/2+1];
dp[0][0]=true;
for(int i=1;i<stones.length+1;i++)
{
for(int j = 0;j<sum/2+1;j++)
{ if(dp[i-1][j])
{ dp[i][j]=dp[i-1][j];
if(j+stones[i-1]<sum/2+1){
dp[i][j+stones[i-1]]=true;
}
}
}
}
int result = 0;
for(int k = sum/2;k>=0;k--)
{//System.out.println(k);
// System.out.println(dp[stones.length][k]);
if(dp[stones.length][k])
{result=k;
break;}
}
// System.out.println(result);
return sum-2*result;
}
}
需要考虑的是如何通过一个归纳法把视角从单个引入整体，发现最后放石头总能变成一定的+1和-1，再通过动态规划和分堆的思想找出上界sum/2，最后可以转化为0-1背包
2022-6-3 322 零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount==0)return 0;//等于0就直接return0了
int[]dp = new int[amount+1];
dp[0]=0;
Arrays.sort(coins);
for(int i =0;i<coins.length;i++)
{
if(coins[i]>amount)continue;//需要这步，太大的硬币价值会溢出
for(int p=0;p<dp.length;p++)
{
int num=1;
if(p==0||dp[p]!=0)//边界注意捏
{
while(p+num*coins[i]<=amount)
{
dp[p+num*coins[i]]=dp[p+num*coins[i]]==0?dp[p]+num:Math.min(dp[p+num*coins[i]],dp[p]+num);
num++;//用每次的最小值来达到最少硬币的效果
}
}
}
}
if(dp[amount]==0)return -1;
return dp[amount];
}
}
本质是一个多重背包问题，本质在于物品可以有无限多个，这时候每次的状态最优就变成了最小值。
- 边界在于只有0个的时候，和amount为0需要做区分。
- 最优子状态：现在就是最小，需要被上一个加上一定的倍数来更新。
- 重叠子问题在这里不做赘述
public class Solution { public int coinChange(int[] coins, int amount) { int max = amount + 1; int[] dp = new int[amount + 1]; Arrays.fill(dp, max); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (coins[j] <= i) { dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);//用减不要用加，用amount*12不要用n倍 } } } return dp[amount] > amount ? -1 : dp[amount]; } }2022-6-4 518 零钱兑换2
改进的多重背包，其实只要加等于之前那个就好。class Solution { public int change(int amount, int[] coins) { int[] dp =new int[amount+1]; dp[0]=1; for(int i = 0;i<coins.length;i++) { for(int j =0;j<dp.length;j++) { if(dp[j]!=0&&j+coins[i]<dp.length) { dp[j+coins[i]]+=dp[j]; } } } return dp[amount]; } }坑
不能先遍历金额，之前的金额可能是会改变的。
若有收获，就点个赞吧
0 人点赞
