背包问题(Knapsack problem)
背包问题指这样一类问题，题意往往可以抽象成：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
维基百科
部分背包问题
问题描述
部分背包问题和0/1背包问题的区别就是：部分背包问题中的单个物品，可以取一部分装入背包。而0/1背包问题则是要么全部拿走，要么一无所有
Subset Sum Problem
问题描述
If for each item the profit and weight are equal, we get the subset sum problem
Given a set of N (N≤40) integers each of them is at most 1012 determine the largest sum subset having sum less than or equal S (S≤1018)
0/1背包问题
问题描述
有N件物品和一个容量为V的背包。第i件物品的费用（即体积，下同）是w[i]，价值是val[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
贪心算法
贪心算法的解不一定是最优解，但是可以作为剪枝一个条件
动态规划
公式
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + val[i])
i <= N and j <= V
空间复杂度优化,利用一维数组进行记忆化，我们只需要使用到当前位置的值和该位置之前的值,从后向前依次计算结果
for (int i = 0; i < N; i++) { for (int j = V; j >= w[i]; j--) { dp[j] = Math.max(dp[j], dp[j - w[i]]+val[i]); } }
回溯算法DFS
剪枝
1.w==0
2.if ((ans - d)(v)[index].weight >= w (v)[index].desirability),使用粗略剪枝会超时，不靠谱
3.index w d 下一直往背包装，能够取得的最大值和当前的ans比较大小，小于当前ans 剪枝
分支限界法
0/1背包物品(无物品价值)
问题描述
假设有一个能装入容量为C的背包和n件重量分别为w1,w2,,…,wn的物品，能否从n件物品中挑选若干件恰好装满背包,要求找出所有满足上述条件的解。
硬币问题是此背包问题的一个特殊解，物品数量的最小值
完全背包问题
问题描述
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是val[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
动态规划
公式
dp[v] = Math.max(dp[v], dp[v-w[i] j] + val[i] j)
0<j<=V/w[i]
动态规划
公式
dp[v] = Math.max(dp[v], dp[v-w[i]] + val[i])
多重背包问题
问题描述
N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是w[i]，价值是val[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
动态规划
公式
dp[v] = Math.max(dp[v], dp[v-w[i] j] + val[i] j)
0<j<=n[i]
二维费用背包问题
问题描述
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为c[i]。
动态规划
公式
dp[v][u] = Math.max(dp[v][u], dp[v-a[i] j][u - b[i] j] + val[i] * j)
0<j<=V/a[i] and 0<j<=U/b[i]
分组背包问题
问题描述
有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是c[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
有依赖的背包问题
问题描述
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。
求背包问题的方案总数
问题描述
对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
参考
Knapsack_problem
list_of_knapsack_problems
List_of_knapsack_problems