0 - 1 背包问题是一个经典的组合优化问题，具有广泛的应用，以下是关于它的详细介绍：

一、问题描述

1. 基本设定

• 有一个容量为的背包。

• 有个物品，每个物品（）有其重量和价值。

• 对于每个物品，只能选择放入背包（选择 1）或者不放入背包（选择 0），这就是 “0 - 1” 名称的由来。

2. 目标

• 在满足背包容量限制的前提下，选择一些物品放入背包，使得背包内物品的总价值最大。

二、解决方法

1. 暴力解法（穷举法）

• 时间复杂度为，当物品数量较大时，计算量会呈指数级增长，效率极低。

• 对于每个物品都有两种选择（放入背包或不放入背包），所以总共有种可能的组合。

• 逐一计算每种组合下背包内物品的总重量和总价值，在总重量不超过背包容量的组合中，找到总价值最大的组合。

2. 动态规划法

• 时间复杂度为，相比于暴力解法，在处理大规模数据时效率更高。

• 通常按照从到，从到的顺序进行计算。

• 当（即背包容量小于第个物品的重量）时，，这意味着第个物品不能放入背包，最大价值与前个物品在容量下的最大价值相同。

• 当时，。这里表示不放入第个物品时的最大价值，表示放入第个物品后的最大价值（是前个物品在剩余容量下的最大价值，加上第个物品的价值）。

• 设表示前个物品，背包容量为时能获得的最大价值。

3. 记忆化搜索（递归 + 记忆化）

• 本质上是动态规划的一种递归实现形式，时间复杂度也为。

• 递归地解决子问题，但为了避免重复计算，使用一个数组（或哈希表）来记录已经计算过的子问题的解。

三、应用场景

1. 资源分配问题

• 例如，一家公司有一定的预算，有个项目可以投资，每个项目需要投入的资金为，预期收益为。公司需要决定投资哪些项目，以在预算范围内获得最大收益，这就可以看作是一个 0 - 1 背包问题。

2. 货物装载问题

• 有一辆载重量为的货车，有种货物可供装载，每种货物的重量为，价值为。要确定装载哪些货物，使货车在不超载的情况下运输货物的总价值最大。

模板：

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是v[i]，得到的价值是w[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

#include <bits/stdc++.h>

using namespace std;

int n, V, ans, v[1005], w[1005];

int dp[1005]; 

// 状态定义 dp[i][j]表示讨论第i个物品，背包容量为j时，能取到的最大价值

// 状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);

// 常用滚动数组优化一维 dp[j] = max(dp[j], dp[j-v[i]] + w[i]);

int main() {

cin >> n >> V;

for (int i = 1; i <= n; i++) {

cin >> v[i] >> w[i];

}

for (int i = 1; i <= n; i++) {

for (int j = V; j >= v[i]; j--) {

dp[j] = max(dp[j], dp[j-v[i]] + w[i]);

}

}

cout << dp[V];

return 0;

}