0-1背包问题，《算法导论》中是这样说明的，一个正在抢劫商店的小偷发现了N个商品，第i个商品价值v[i]美元，重w[i]磅，v[i]和w[i]都是整数。这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅重的商品，W是一个整数。他该怎么拿？（对每个商品，小偷要么把它完整拿走，要么把它留下，他不能只拿走一个商品的一部分，或者把一个商品拿走多次。）
之前说过“两个CPU核分配任务问题”，给定n(0~N)个任务work，每个任务i=0~n-1都有各自需要处理的时间needTime[i] =1~1000(ms)。另外有两个CPU核（核A、核B）处理这些任务，将n个任务分配给两个CPU核，求这两个核处理完所有给定任务所需要的最短时间。（其中，每个任务只能分配给一个核进行处理，且只被能处理一次。每个CPU核同一时间只能处理一个任务。）
第二个问题本质上就是第一个问题，N个任务work就是N个商品，任务所需的处理时间needTime[i] 就是商品的重量w[i]，而两个CPU核就是小偷的背包，只不过这里的任务没有价值，不过我们可以将价值和任务的处理时间看作同一个，即任务的价值还是needTime[i]，对应于商品的价值v[i]。显而易见，我们可以使用0-1背包的解决方法解决“两个CPU核任务分配问题”。
另外，这里需要注意，我们把处理任务总时间较短那个核（假设为 核A）看作一个背包，因为所有任务的总时间不变，只需求出核A，核B也自然得到。核A的解越大，核B的解越小。核B得到最小的解时，便得到了问题的解。
解析0-1背包问题：
0-1背包问题的解决思路是使用动态规划，设dp[i][j]表示存在前 i 件商品，背包的容量为W == j 时，的最优解。动态规划是在子问题dp[ik][jk]（ik<i , jk<j）得到最优解后求解当前dp[i][j]的最优解的过程。关键是想明白dp[i][j]与dp[ik][jk]之间的关系，从商品的角度来思考即：
1.当背包 j 无法容下 i 商品时（w[i]>j）时，那么当前dp[i][j]的最优解就和没有 i 商品一样，即dp[i][j]=dp[i - 1][j]；
2.当背包 j 可以容下 i 商品时（w[i]<=j）时，我们要判断，以最佳的方式塞下 i 商品得到的价值（dp[i - 1][j - weight[i]] +value[i]），和没有 i 商品时的最优解dp[i - 1][j]，哪个价值更高，采用这两者价值更高的方案。
下面是“0-1背包”的算法，和使用该算法解决上面的“两个CPU核任务分配的问题”：
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// 0-1背包问题
int getMaxValue(const vector<int>& weight, const vector<int>& value, int packet)
{
int len = weight.size();
vector<vector<int> > dp(len + 1, vector<int>(packet + 1, 0));
for (int j = 1; j <= packet; j++)
for (int i = 1; i <= len; i++)
if (weight[i - 1] <= j)
dp[i][j] = max(dp[i - 1][j - weight[i - 1]] + value[i - 1], dp[i - 1][j]);// 当背包 j 可以容下 i 商品时（w[i]<=j）时，我们要判断，以最佳的方式塞下 i 商品得到的价值（dp[i - 1][j - weight[i]] + value[i]），和没有 i 商品时的最优解dp[i - 1][j]，哪个价值更高，采用这两者价值更高的方案
else
dp[i][j] = dp[i - 1][j];// 当背包 j 无法容下 i 商品时（w[i]>j）时，那么当前dp[i][j]的最优解就和没有 i 商品一样
return dp[len][packet];
}
int main()
{
int n, num;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> num;
nums.push_back(num);
}
int sum = accumulate(nums.begin(), nums.end(), 0);// 所有任务的总时间
int half = static_cast<int>(sum / 2);// 处理任务总时间较短那个核，的最大的容量
cout << sum - getMaxValue(nums, nums, half) << endl;
return 0;
}