# Backpack C++ Solution Summary

• 1 Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
int backPack(int m, vector<int> A) {
// table[i][j] denotes whether using the first elements
// could fulfill size j.
vector<vector<bool>> dp(A.size() + 1, vector<bool>(m + 1, false));
if(m == 0 || A.size() == 0) {
return 0;
}
for(int i = 0; i < m + 1; i++)   dp[0][i] = false;

for(int i = 0; i < A.size() + 1; i++)  dp[i][0] = true;

for(int i = 1; i < A.size() + 1; i++) {
for(int j = 1; j < m + 1; j++) {
if(j - A[i-1] < 0) {
dp[i][j] = dp[i - 1][j];
}
else {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
}
}
}

for(int i = m; i >= 0; i--) {
if (dp[A.size()][i]) {
return i;
}
}
return 0;
}
};

2 Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A & V: Given n items with size A[i] and value V[i]
* @return: The maximum value
*/
int backPackII(int m, vector<int> A, vector<int> V) {
vector<vector<int>> dp(A.size() + 1, vector<int>(m + 1, false));
if(m == 0 || A.size() == 0) {
return 0;
}

for(int i = 0; i < m + 1; i++)   dp[0][i] = 0;
for(int i = 0; i < A.size() + 1; i++)  dp[i][0] = 0;

for(int i = 1; i < A.size() + 1; i++) {
for(int j = 1; j < m + 1; j++) {
if(j - A[i-1] < 0) {
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[A.size()][m];
}
};

3 Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

class Solution {
public:
/**
* @param nums an integer array and all positive numbers, no duplicates
* @param target an integer
* @return an integer
*/
int backPackVI(vector<int>& nums, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (const auto& num : nums) {
if (i >= num) {
dp[i] += dp[i - num];
}
}
}
return dp.back();
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.