首页 > 代码库 > HDu -2844 Coins多重背包
HDu -2844 Coins多重背包
这道题是典型的多重背包的题目，也是最基础的多重背包的题目
题目大意：给定n和m， 其中n为有多少中钱币， m为背包的容量，让你求出在1 - m 之间有多少种价钱的组合，由于这道题价值和重量相等，所以就是dp[i] = i， 其中dp[i]表示当前背包容量为i 的时候背包能装的价值。
题目思路： 模板 二进制优化
话说那个二进制真的很奇妙，只需要2的1次方 到 2的k-1次方， 到最后在加上一项当前项的个数 - 2 的k次方 + 1，也就是这些系数分别为1; 2; 22 .....2k-1;Mi - 2k + 1，且k是满足Mi - 2k + 1 > 0的最大整数, 就能表示出所有1 - Mi之间的所有系数，好强大～
代码如下：
1 #include<iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int MAX = 100000; 6 int dp[MAX]; 7 int c[MAX], w[MAX]; 8 int v; 9 10 void ZeroOnePack(int cost, int wei)11 {12 for (int i = v; i >= cost; i--)13 dp[i] = max(dp[i], dp[i - cost] + wei);14 }15 16 void CompletePack(int cost, int wei)17 {18 for (int i = cost; i <= v; i++)19 dp[i] = max(dp[i], dp[i - cost] + wei);20 }21 22 void MultiPack(int cost, int wei, int cnt)23 {24 if (v <= cnt * cost)//如果个数*重量大于背包容量了，直接完全背包25 {26 CompletePack(cost, wei);27 }28 else29 {30 int k = 1;31 while (k <= cnt)32 {33 ZeroOnePack(k *cost, k * wei);34 cnt = cnt - k;35 k = 2 * k;36 }37 ZeroOnePack(cnt * cost, cnt * wei);38 }39 }40 41 int main()42 {43 44 int n;45 while (~scanf("%d %d", &n, &v), n + v)46 {47 for (int i = 0; i < n; i++)48 scanf("%d", &c[i]);49 for (int i = 0; i < n; i++)50 scanf("%d", &w[i]);51 memset(dp, 0, sizeof(dp));52 for (int i = 0; i< n; i++)53 {54 MultiPack(c[i], c[i], w[i]);55 56 }57 int sum = 0;58 for (int i = 1; i <= v; i++)59 if (dp[i] == i)60 sum++;61 printf("%d\n", sum);62 63 }64 65 return 0;66 }
HDu -2844 Coins多重背包
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。