https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/description/
Notes:
This question belongs to knapsack problem.
Since each element (or digit) can be used as many times as needed, so it is a 01 knapsack problem.
To form the largest number, the first step should find the longest digits that can be formed, this is a typical knapsack problem.
After finding the longest digits that can be formed, we can greedily add the digits from the larger one to the smaller one.
One of the key condition for the greedy way:
dp[target] = 1 + dp[target - cost[i]]
where dp[target] is the length of the longest digits that can be formed.
This equation means that: after taking the largest digit available at this moment, the rest part (target - cost[i]) can still matches the longest digits overall. Thus, it can always give the optimal solution.
See the code below:
class Solution {
public:
string largestNumber(vector<int>& cost, int target) {
vector<int> dp(target+1, -5000);
dp[0] = 0;
for(int i=0; i<=target; ++i) {
for(int j=0; j<9; ++j) {
if(i>= cost[j]) dp[i] = max(dp[i], 1 + dp[i - cost[j]]);
}
}
if(dp[target]<=0) return "0";
// cout<<dp[target]<<endl;
string res = "";
for(int i=8; i>=0; --i) {
while(target>=cost[i] && dp[target] == 1 + dp[target - cost[i]]) {
res.push_back(i+1+'0');
target -= cost[i];
}
}
return res;
}
};
No comments:
Post a Comment