粉红色主题 模板 网站 在线预览,如何搭建一个网站平台,网站建设教程 迅雷下载,国外企业网页设计混合背包是指多种背包模型的组合与转化。
下面通过题目加深理解。 题目一
测试链接#xff1a;1742 -- Coins
分析#xff1a;这道题可以通过硬币的个数将其转化为01背包#xff0c;完全背包和多重背包。如果硬币的个数是1个#xff0c;则是01背包#xff1b;如果硬币的…混合背包是指多种背包模型的组合与转化。
下面通过题目加深理解。 题目一
测试链接1742 -- Coins
分析这道题可以通过硬币的个数将其转化为01背包完全背包和多重背包。如果硬币的个数是1个则是01背包如果硬币的面值×硬币的个数大于当前需要找零的数额则是完全背包否则是多重背包。对于不同的背包进行不同的可能性展开最后统计即可得到答案。代码如下。
#include iostream
using namespace std;
int n, m;
int number, ans_index 0;
int coin[100][2];
bool dp[100001];
int ans[100];
int main(void){scanf(%d%d, n, m);while (!(n 0 m 0)){number 0;for(int i 0;i n;i){scanf(%d, coin[i][0]);}for(int i 0;i n;i){scanf(%d, coin[i][1]);}for(int i 1;i m;i){dp[i] false;}dp[0] true;for(int i 0;i n;i){if(coin[i][1] 1){for(int j m;j 0 j - coin[i][0] 0;--j){dp[j] | dp[j-coin[i][0]];}}else if(coin[i][0] * coin[i][1] m){for(int j 0;j m;j){if(j - coin[i][0] 0){dp[j] | dp[j-coin[i][0]];}}}else{for(int j m;j 0;--j){for(int k 1;k coin[i][1] j - k * coin[i][0] 0;k){dp[j] | dp[j-k*coin[i][0]];}}}}for(int i 1;i m;i){if(dp[i]){number;}}ans[ans_index] number;scanf(%d%d, n, m);}for(int i 0;i ans_index;i){printf(%d\n, ans[i]);}return 0;
}其中求dp数组循环中i为在下标0~i的物品中取。当然这道题其实可以直接将其当作一个多重背包二进制优化后转化为01背包进行求解。代码如下。
#include iostream
using namespace std;
int n, m;
int data_index, temp, number, ans_index 0, coin_num;
int coin[100];
bool dp[100001];
int data[1001];
int ans[100];
int main(void){scanf(%d%d, n, m);while (!(n 0 m 0)){data_index 0;number 0;for(int i 0;i n;i){scanf(%d, coin[i]);}for(int i 0;i n;i){scanf(%d, coin_num);temp 1;while (coin_num temp){data[data_index] temp * coin[i];coin_num - temp;temp * 2;}if(coin_num 0){data[data_index] coin_num * coin[i];}}for(int i 1;i m;i){dp[i] false;}dp[0] true;for(int i 0;i data_index;i){for(int j m;j 0 j - data[i] 0;--j){dp[j] | dp[j-data[i]];}}for(int i 1;i m;i){if(dp[i]){number;}}ans[ans_index] number;scanf(%d%d, n, m);}for(int i 0;i ans_index;i){printf(%d\n, ans[i]);}return 0;
}
