本文主要总结Lintcode的Backpack Problem I - VI. Backpack的解题思路是建立二维表。fill matrix。用到dp[i][j] 的二维DP数组。
Backpack I:
www.lintcode.com/problem/backpack
设dp[i][j] 为前Item I，取size <= j 的最大值，则有两种可能。1. 不拿item i，dp[i][j] = dp[i-1][j]; 2. 拿item i，dp[i][j] = dp[i-1][j-A[i]] + A[i]。所以通项公式为：
dp[i][j] = max(dp[i-1][j] + dp[i-1][j-A[i]] + A[i])
int backPack(int m, vector<int> A) {
// write your code here
if(A.empty()) return 0;
int n = A.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(j < A[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + A[i-1]);
}
}
}
return dp[n][m];
}
Backpack II:
http://www.lintcode.com/en/problem/backpack-ii/#
题中加入了value元素，基本没有变化。dp[i][j] 为前i个，组成size <= j的最大value值，所以通项改为
dp[i][j] = max(dp[i-1][j] + dp[i-1][j-A[i]] + V[i])
int backPackII(int m, vector<int> A, vector<int> V) {
// write your code here
if(m <= 0 || A.empty() || A.size() != V.size()) return 0;
int n = A.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(j < A[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
}
}
}
return dp[n][m];
}
Backpack III:
http://www.lintcode.com/en/problem/backpack-iii/#
Backpack III 是无限背包，表示每一个item可以取无数次。
所以通项定义稍有变化。dp[i][j] 为当前到第i个item，拿到size <= j 的最大价值。所以有最后不取第i个item，dp[i][j] = dp[i-1][j], 取第i个item，由于之前也可以取item i，dp[i][j] = dp[i][j-A[i]] + A[i]
通项公式为：
dp[i][j] = max(dp[i-1][j] + dp[i][j-A[i]] + A[i])
int backPackIII(vector<int>& A, vector<int>& V, int m) {
// Write your code here
if(m <= 0 || A.empty() || A.size() != V.size()) return 0;
int n = A.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(j < A[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-A[i-1]] + V[i-1]);
}
}
}
return dp[n][m];
}
Backpack IV:
http://www.lintcode.com/en/problem/backpack-iv/#
求方案个数，求方案个数就是把取max，变成求和。由于还是无限背包，即每个item可以用无数次，所以还是看同一行。通项公式如下：
dp[i][j] 为取到前i个数，组成size <= j 的总方案个数。
dp[i][j] = dp[i-1][j] + dp[i][j-A[i]];
初始化时，要把起始整个column都设为1.
int backPackIV(vector<int>& nums, int target) {
// Write your code here
if(nums.empty()) return 0;
int n = nums.size();
vector<vector<int>> dp(n+1, vector<int>(target+1, 0));
for(int i=1; i<=n; i++){
dp[i][0] = 1;
for(int j=1; j<=target; j++){
if(j < nums[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-nums[i-1]];
}
}
}
return dp[n][target];
}
Backpack V:
http://www.lintcode.com/en/problem/backpack-v/
这道题就是与IV相比，去掉了无限背包的条件，每个item用一次。
dp[i][j] 为前i个item，去size <= j 的方案个数。通项公式为
dp[i][j] = dp[i-1][j] + dp[i-1][j-A[i]]; 与I and II 类似。
int backPackV(vector<int>& nums, int target) {
// Write your code here
if(nums.empty() || target <= 0) return 0;
int n = nums.size();
vector<vector<int>> dp(n+1, vector<int>(target+1, 0));
dp[0][0] = 1;
for(int i=1; i<=n; i++){
dp[i][0] = 1;
for(int j=1; j<=target; j++){
if(j<nums[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
}
或者用下面的方法
int findSum(vector<int>& nums, int target){
int len = nums.size();
int *dp = new int[target+1];
fill_n(dp, target+1, 0);
dp[0] = 1;
for(int i=0; i<nums.size(); i++){
for(int j=target; j>=nums[i]; j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[target];
}
Backpack VI:
http://www.lintcode.com/en/problem/backpack-vi/
这道题就是combination sum，代码如下:
int backPackVI(vector<int>& nums, int target) {
// Write your code here
if(target <= 0 || nums.empty()) return 0;
int n = nums.size();
vector<int> dp(target+1, 0);
dp[0] = 1;
for(int i=1; i<=target; i++){
for(int j=0; j<n; j++){
if(i >= nums[j]) dp[i] += dp[i-nums[j]];
}
}
return dp[target];
}
