首页 > 代码库 > PAT 1068. Find More Coins
PAT 1068. Find More Coins
标准10背包
#include <cstdio>#include <cstdlib>#include <vector>#include <algorithm>using namespace std;const int ROWS = 10002;const int COLS = 102;char dp[ROWS][COLS];bool dfs(vector<int> &coins, vector<int> &path, int idx, int target) { if (dp[idx][target] != -1) { return dp[idx][target]; } if (idx >= coins.size()) return false;// should not happen if (coins[idx] == target) { // we found one path.push_back(idx); return true; } if (idx == coins.size() - 1) { // no more coins to try return false; } path.push_back(idx); // try use current idx coin if (coins[idx] < target) { if (dfs(coins, path, idx + 1, target - coins[idx])) { return true; } } path.pop_back(); // try not use current idx coin if (dfs(coins, path, idx + 1, target)) { return true; } dp[idx][target] = false; return dp[idx][target];}int main() { int N, M; scanf("%d%d", &N, &M); vector<int> coins(N); for (int i=0; i<N; i++) { scanf("%d", &coins[i]); } sort(coins.begin(), coins.end()); for (int i=0; i<ROWS; i++) { for (int j=0; j<COLS; j++) { dp[i][j] = -1; } } // use current st. j-coins>=0 //dp[i][j] = dp[i-1][j-coins[i]] // not use current //dp[i][j] = dp[i-1][j]; vector<int> path; bool res = dfs(coins, path, 0, M); int len = path.size(); if (res) { if (len > 0) { printf("%d", coins[path[0]]); } for (int i=1; i<len; i++) { printf(" %d", coins[path[i]]); } } else { printf("No Solution"); } return 0;}
PAT 1068. Find More Coins
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。