小说短篇做的好的网站,小程序制作那个好,房产咨询律师免费咨询,免费网站建设ppt模板下载这段代码的主要思路是使用动态规划来构建一个二维数组 dp#xff0c;其中 dp[i][j] 表示前 i 个产品是否可以组合出金额 j。通过遍历产品列表和可能的目标金额#xff0c;不断更新 dp 数组中的值#xff0c;最终返回 dp[N][M] 来判断是否可以组合出目标金额 M。如果 dp[N][M… 这段代码的主要思路是使用动态规划来构建一个二维数组 dp其中 dp[i][j] 表示前 i 个产品是否可以组合出金额 j。通过遍历产品列表和可能的目标金额不断更新 dp 数组中的值最终返回 dp[N][M] 来判断是否可以组合出目标金额 M。如果 dp[N][M] 为 true则表示可以组合出目标金额否则表示无法组合出目标金额。
#include iostream
#include vector
#include limitsusing namespace std;bool miHomeGiftBag(vectorint p, int M) {int N p.size(); // 获取产品列表中产品的数量vectorvectorbool dp(N 1, vectorbool(M 1, false)); // 创建一个二维动态规划数组dp[i][j] 表示前 i 个产品是否能够组合出金额 jdp[0][0] true; // 初始化金额为0时总是可以组合出来for (int i 1; i N; i) { // 遍历产品列表for (int j 0; j M; j) { // 遍历可能的目标金额dp[i][j] dp[i - 1][j]; // 初始情况不使用当前产品 iif (j - p[i - 1] 0) { // 如果当前目标金额 j 大于等于当前产品的价格// 尝试使用当前产品 i判断前 i-1 个产品是否可以组合出目标金额 j - p[i-1]dp[i][j] dp[i - 1][j - p[i - 1]] || dp[i][j];}}}return dp[N][M]; // 返回 dp[N][M]表示前 N 个产品是否可以组合出目标金额 M
}int main() {bool res;int _p_size 0;cin _p_size;cout _p_size endl;vectorint _p;int _p_item;for(int _p_i0; _p_i_p_size; _p_i) {cin _p_item;cin.ignore (std::numeric_limitsstd::streamsize::max(), \n);_p.push_back(_p_item);}int _M;cin _M;cin.ignore (std::numeric_limitsstd::streamsize::max(), \n);res miHomeGiftBag(_p, _M);cout res endl;return 0;}
