本文主要總結(jié)Lintcode的Backpack Problem I - VI. Backpack的解題思路是建立二維表猿推。fill matrix谴分。用到dp[i][j] 的二維DP數(shù)組格仲。
Backpack I:
www.lintcode.com/problem/backpack
設(shè)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]。所以通項(xiàng)公式為：
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個(gè)，組成size <= j的最大value值纺裁，所以通項(xiàng)改為
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 是無限背包诫肠，表示每一個(gè)item可以取無數(shù)次。
所以通項(xiàng)定義稍有變化欺缘。dp[i][j] 為當(dāng)前到第i個(gè)item栋豫，拿到size <= j 的最大價(jià)值。所以有最后不取第i個(gè)item谚殊，dp[i][j] = dp[i-1][j], 取第i個(gè)item笼才，由于之前也可以取item i，dp[i][j] = dp[i][j-A[i]] + A[i]
通項(xiàng)公式為：
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/#
求方案個(gè)數(shù)络凿，求方案個(gè)數(shù)就是把取max骡送，變成求和。由于還是無限背包絮记，即每個(gè)item可以用無數(shù)次摔踱，所以還是看同一行。通項(xiàng)公式如下：
dp[i][j] 為取到前i個(gè)數(shù)怨愤，組成size <= j 的總方案個(gè)數(shù)派敷。
dp[i][j] = dp[i-1][j] + dp[i][j-A[i]];
初始化時(shí)，要把起始整個(gè)column都設(shè)為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相比撰洗，去掉了無限背包的條件篮愉，每個(gè)item用一次。
dp[i][j] 為前i個(gè)item差导，去size <= j 的方案個(gè)數(shù)试躏。通項(xiàng)公式為
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];
}
