一、01背包：每个物品最多拿一个

1. 什么时候用01背包？

• 题目明确限制每个元素最多用一次。

• 要求选或不选得到某种极值（最大价值、能否凑满、方案数）。

2. 怎么把问题转化成01背包？

第一步：找“背包容量”

你要凑的目标值是什么？比如“总和的一半”、“子集和”、“总字符串长度”等，这就是背包的最大容量。

第二步：找“物品”

数组里的每个元素，比如石头重量、数字值、字符串（带有0和1的个数），它们都有重量，有的还有价值（价值通常等于重量，或者为1表示个数）。

第三步：定义dp含义

• 求最大价值：dp[j] = 容量为j时的最大价值。

• 能否装满：dp[j] = 容量j是否能恰好被填满（布尔值或int 0/1）。

• 装满的方案数：dp[j] = 装满容量j的方法数。

由于物品只有一个，所以遍历背包容量的时候要倒序遍历，避免重复选择

3.例题：

1049.最后一块石头的重量II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；

• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

转化：两堆石头血拼，那不得让他们势均力敌？

所以问题变成：有一堆石头（物品），每个只能选一次，背包容量设为sum/2，求最多能装多重。最后剩下= sum - dp[target] - dp[target]。

 int lastStoneWeightII(int *stones, int stonesSize)
 {
     int sum = 0;
     for (int i = 0; i < stonesSize; i++)
     {
         sum += stones[i];
     }
     int target = sum / 2;
     int *dp = (int *)calloc(1501, sizeof(int)); 
     for (int i = 0; i < stonesSize; i++)
     {
         for (int j = target; j >= stones[i]; j--)
         {
             dp[j] = fmax(dp[j], dp[j - stones[i]] + stones[i]);
         }
     }
     return sum - dp[target] - dp[target];
 }

494.目标和

题目

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

转化：

假设加法的总和为 left ，那么减法对应的总和就是 sum - left 。所以我们要求的是left - (sum - left) = target，即 left= (target + sum) / 2,此时问题就转化为，用nums数组装满容量为left 的背包，有几种方法。

 int findTargetSumWays(int *nums, int numsSize, int target)
 {
     int sum = 0;
     for (int i = 0; i < numsSize; i++)
     {
         sum += nums[i];
     }
     int left = (sum + target) / 2; // left表示正数和
     if (left * 2 != sum + target || sum < target || left < 0)
     {
         return 0;
     }
 ​
     int *dp = (int *)calloc(left + 1, sizeof(int));
     dp[0] = 1;
     for (int i = 0; i < numsSize; i++)
     {
         for (int j = left; j >= nums[i]; j--)
         {
             dp[j] += dp[j - nums[i]];
         }
     }
     return dp[left];
 }

---

二、完全背包：物品可以重复使用

1. 关键细节：求组合数 vs 求排列数

• 求组合数：先遍历物品，再遍历容量。

• 求排列数：先遍历容量，再遍历物品。

2.什么时候用完全背包？

• 物品可以无限次使用。

• 常见于硬币找零、整数拆分、爬楼梯（每次可跨任意步数）。

3. 怎么把问题转化成完全背包？

同样的三步法，但物品是无限的，所以容量正序。

4.例题

518. 零钱兑换 II

题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

思路

求凑出amount的硬币组合数。硬币无限个，完全背包。因为是组合数，所以代码外层循环是coins，内层是amount正序：

 for (int i = 0; i < coinsSize; i++) {
     for (int j = coins[i]; j <= amount; j++) {
         dp[j] += dp[j - coins[i]];
     }
 }

377. 组合总和 Ⅳ 

题目

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素排列的个数。

思路

虽然叫“组合总和”，但题目强调顺序不同算不同组合，其实是排列。所以先遍历容量再遍历物品：

 for (int j = 0; j <= target; j++) {           // 容量在外
     for (int i = 0; i < numsSize; i++) {      // 物品在内
         if (j >= nums[i]) dp[j] += dp[j - nums[i]];
     }
 }

---

三、总结：背包问题转化

1. 找容量：题目要你达到的“总数”、“目标值”、“限制条件”是啥？那就是背包容量。

2. 找物品：数组里的每个元素有什么属性？它占据多少容量？能带来什么价值？

3. 定规则：

   • 每个物品只能用一次 → 01背包（容量倒序）。

   • 每个物品无限用 → 完全背包（容量正序）。

   • 求最大价值 → max。

   • 求能不能 → dp[j]用布尔值。

   • 求方案数 → dp[0]=1，累加。