经典动态规划：0-1 背包问题
背包问题：
class solution {
public:
//今天就来说一下背包问题吧，就讨论最常说的 0-1 背包问题，简单描述一下吧：
//给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。
//其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
//举个简单的例子，输入如下：
/*N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]*/
int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
// vector 全填入 0，base case 已初始化
vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w - wt[i - 1] < 0) {
// 当前背包容量装不下，只能选择不装入背包
dp[i][w] = dp[i - 1][w];
}
else {
// 装入或者不装入背包，择优
dp[i][w] = max(dp[i - 1][w - wt[i - 1]] + val[i - 1],
dp[i - 1][w]);
}
}
}
return dp[N][W];
}
};
上一篇：
IDEA上Java项目控制台中文乱码