91. 最小調整代價
給一個整數陣列，調整每個數的大小，使得相鄰的兩個數的差不大于一個給定的整數target，
調整每個數的代價為調整前后的差的絕對值，求調整代價之和最小是多少，
樣例 1:
輸入: [1,4,2,3], target=1
輸出: 2
樣例 2:
輸入: [3,5,4,7], target=2
輸出: 1
'''
class Solution {
public:
/**
* @param A: An integer array.
* @param target: An integer.
*/
int MinAdjustmentCost(vector<int> A, int target) {
// write your code here
int array1[101], array2[101], *p = array1, *q = array2;
for (int i = 1; i <= 100; ++i) p[i] = abs(A[0] - i);
for (int i = 1; i < A.size(); ++i) {
int minval[101], l = 0, r = -1;
for (int j = 1; j <= target && j <= 100; ++j) {
while (r >= l && p[minval[r]] >= p[j]) --r;
minval[++r] = j;
}
for (int j = 1; j <= 100; ++j) {
if (j + target <= 100) {
while (r >= l && p[minval[r]] >= p[j + target]) --r;
minval[++r] = j + target;
}
if (minval[l] < j - target) ++l;
q[j] = abs(A[i] - j) + p[minval[l]];
}
swap(p, q);
}
int ans = p[1];
for (int i = 2; i <= 100; ++i) {
if (ans > p[i]) ans = p[i];
}
return ans;
}
};
'''
92. 背包問題
描述
在n個物品中挑選若干物品裝入背包，最多能裝多滿？假設背包的大小為m，每個物品的大小為A[i]
樣例 1:
輸入: [3,4,8,5], backpack size=10
輸出: 9
樣例 2:
輸入: [3,5,4,7], target=2
輸出: 1
'''
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) {
// write your code here
int n = A.size();
bool dp[m + 1];
dp[0] = true;
for(int i = 1; i <= m; i++){
dp[i] = false;
}
for(int i = 1; i <= n; i++){
for(int j = m; j >= A[i - 1]; j--){
dp[j] = dp[j] || dp[j - A[i - 1]];
}
}
for(int i = m; i >= 0; i--){
if(dp[i]){
return i;
}
}
}
};
'''
125. 背包問題 II
有 n 個物品和一個大小為 m 的背包. 給定陣列 A 表示每個物品的大小和陣列 V 表示每個物品的價值.問最多能裝入背包的總價值是多大?
- A[i], V[i], n, m 均為整數
- 你不能將物品進行切分
- 你所挑選的要裝入背包的物品的總大小不能超過 m
- 每個物品只能取一次
樣例 1:
輸入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
輸出: 9
解釋: 裝入 A[1] 和 A[3] 可以得到最大價值, V[1] + V[3] = 9
樣例 2:
輸入: m = 10, A = [2, 3, 8], V = [2, 5, 8]
輸出: 10
解釋: 裝入 A[0] 和 A[2] 可以得到最大價值, V[0] + V[2] = 10
class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
int backPackII(int m, vector<int> &A, vector<int> &V) {
// write your code here
int n=A.size();
if(n==0){
return 0;
}
vector<vector<int>> dp(n+1, vector<int>(m+1));
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
}
else if (A[i - 1] > j) {
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];
}
};
562. 背包問題 IV
給出 n 個物品, 以及一個陣列, nums[i]代表第i個物品的大小, 保證大小均為正數并且沒有重復, 正整數 target 表示背包的大小, 找到能填滿背包的方案數，
每一個物品可以使用無數次
樣例1
輸入: nums = [2,3,6,7] 和 target = 7
輸出: 2
解釋:
方案有:
[7]
[2, 2, 3]
樣例2
輸入: nums = [2,3,4,5] 和 target = 7
輸出: 3
解釋:
方案有:
[2, 5]
[3, 4]
[2, 2, 3]
class Solution {
public:
/**
* @param nums an integer array and all positive numbers, no duplicates
* @param target an integer
* @return an integer
*/
int backPackIV(vector<int>& nums, int target) {
// Write your code here
int n = nums.size();
vector<int> dp(target + 1);
dp[0] = 1;
for (int x : nums) {
for (int j = x; j <= target; ++j) {
dp[j] += dp[j - x];
}
}
return dp[target];
}
};
563. 背包問題 V
給出 n 個物品, 以及一個陣列, nums[i] 代表第i個物品的大小, 保證大小均為正數, 正整數 target 表示背包的大小, 找到能填滿背包的方案數，
每一個物品只能使用一次
給出候選物品集合 [1,2,3,3,7] 以及 target 7
結果的集合為:
[7]
[1,3,3]
回傳 2
class Solution {
public:
/**
* @param nums: an integer array and all positive numbers
* @param target: An integer
* @return: An integer
*/
int backPackV(vector<int>& nums, int target) {
// Write your code here
vector<int> dp(target + 1);
dp[0] = 1;
for (auto a : nums) {
for (int i = target; i >= a; --i) {
dp[i] += dp[i - a];
}
}
return dp.back();
}
};轉載請註明出處，本文鏈接：https://www.uj5u.com/net/1656.html