首页 > 代码库 > 百练2755 神奇的口袋 【深搜】or【动规】or【普通递归】or【递推】
百练2755 神奇的口袋 【深搜】or【动规】or【普通递归】or【递推】
3 20 20 20
3
这题很经典,可以用很多方法来做,我试了以下几种:
DFS:耗时0ms
#include <stdio.h> int arr[22], ans, n, sum; void DFS(int k) { if(sum >= 40){ if(sum == 40) ++ans; return; } for(int i = k; i <= n; ++i){ sum += arr[i]; DFS(i + 1); sum -= arr[i]; } } int main() { int i; scanf("%d", &n); for(i = 1; i <= n; ++i) scanf("%d", arr + i); sum = ans = 0; DFS(1); printf("%d\n", ans); return 0; }
普通递归:耗时60ms
#include <stdio.h> int arr[22], n; int getAns(int sum, int k) { if(sum == 0) return 1; if(k == 0) return 0; return getAns(sum, k - 1) + getAns(sum - arr[k], k - 1); } int main() { int i; scanf("%d", &n); for(i = 1; i <= n; ++i) scanf("%d", arr + i); printf("%d\n", getAns(40, n)); return 0; }
DP:耗时0ms
#include <stdio.h> int arr[22], n, dp[42][22]; //dp[i][j]表示从前j种物品里配出价值i的方法数 int main() { int i, j; scanf("%d", &n); for(i = 1; i <= n; ++i){ scanf("%d", arr + i); dp[0][i] = 1; } for(dp[0][0] = i = 1; i <= 40; ++i){ for(j = 1; j <= n; ++j){ dp[i][j] = dp[i][j - 1]; if(i - arr[j] >= 0) dp[i][j] += dp[i - arr[j]][j - 1]; } } printf("%d\n", dp[40][n]); return 0; }
递推型DP:耗时0ms
#include <stdio.h> int n, sum[42]; //sum[i]表示价值能组成i的方法数 int main() { int i, j, temp; scanf("%d", &n); for(i = 0, sum[0] = 1; i < n; ++i){ scanf("%d", &temp); for(j = 40; j; --j){ if(j + temp > 40) continue; if(sum[j]) sum[j + temp] += sum[j]; } ++sum[temp]; } printf("%d\n", sum[40]); return 0; }
百练2755 神奇的口袋 【深搜】or【动规】or【普通递归】or【递推】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。