1068.Find More Coins (30)
pat-al-1068
2017-02-08
啊全是自己寫的竟然一次AC了，好開心啊寫的有點麻煩，如果以后再寫一次的話，會優化一下，參考：1068. Find More Coins (30)-PAT甲級真題有點像0-1背包。說起來慚愧，雖然去年學了動態規劃，卻沒有用dp寫過0-1背包……所以完全不會，只好臨時找了一篇文章看： 動態規劃之01背包問題（最易理解的講解）。看懂了0-1背包問題怎么用dp解決，就會做這題了。/** * pat-al-1068 * 2017-02-08 * Cpp version * Author: fengLian_s */#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;bool cmp(int a, int b){ return a > b;}int main(){ freopen("in.txt", "r", stdin); int n, m; scanf("%d%d", &n, &m); int coin[10002] = {0}, dp[10002][102] = {0}, select[10002][102] = {0}; for(int i = 1;i <= n;i++) { scanf("%d", &coin[i]); } sort(coin+1, coin+n+1, cmp); // for(int i = 1;i <= n;i++)//初始化第一列 // { // if(coin[i] == 1) // { // dp[i][1] = 1; // select[i][1] = 1; // } // } // for(int j = 1;j <= m;j++)//初始化第一行 // { // if(j >= coin[1]) // { // dp[1][j] = coin[1]; // select[1][j] = 1; // } // } for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { if(dp[i-1][j] <= (dp[i-1][j-coin[i]]+coin[i]) && (dp[i-1][j-coin[i]]+coin[i]) <= j) { dp[i][j] = dp[i-1][j-coin[i]]+coin[i]; select[i][j] = 1; } else { dp[i][j] = dp[i-1][j]; select[i][j] = 0; } } } // for(int i = 1;i <= n;i++) // { // for(int j = 1;j <= m;j++) // { // -FIN-新聞熱點
疑難解答
