首页 > 代码库 > 多重背包之 HDU -1171Big Event in HDU &HDU -2191悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
多重背包之 HDU -1171Big Event in HDU &HDU -2191悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
这两道题都是多重背包的基础题，前面的安格题意是:给出每个物体的价值和物体的数量，如何分使得A,B所得价值最接近并且A的价值不能小于B,就类似于NYOJ上的那个邮票分你一半那个意思,只不过这里不是一个而是多个，所以多重背包
前一个题是将总和的一半当作背包的容量来求，代码如下
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int dp[100000]; 8 int cnt[100]; 9 int value[100];10 int main()11 {12 int n;13 while (~scanf("%d", &n) && n > 0)14 {15 memset(dp, 0, sizeof(dp));16 int sum = 0;17 for (int i = 0; i < n; i++)18 {19 scanf("%d %d", &value[i], &cnt[i]);20 sum += value[i] * cnt[i];21 }22 int v = sum / 2;23 for (int i = 0; i < n; i++)24 {25 for (int j = v; j >= value[i]; j--)//01背包26 {27 for (int k = 1; k <= cnt[i] && k * value[i] <= j; k++)//遍历每一种28 dp[j] = max(dp[j], dp[j - k * value[i]] + k * value[i]);29 }30 }31 printf("%d %d\n", sum - dp[v], dp[v]);32 }33 return 0;34 }
第二个题一样的，也是多重背包
代码如下
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 const int N = 150; 7 int weight[N]; 8 int value[N]; 9 int cnt[N];10 int dp[N];11 int main()12 {13 int T;14 int n, money;15 scanf("%d", &T);16 while (T--)17 {18 scanf("%d %d", &money, &n);19 for (int i = 0; i < n; i++)20 scanf("%d %d %d", &weight[i], &value[i], &cnt[i]);21 memset(dp, 0, sizeof(dp));22 for (int i = 0; i < n; i++)23 {24 for (int j = money; j >= weight[i]; j--)//01背包25 {26 for (int k = 1; k <= cnt[i] && k * weight[i] <= money; k++)//遍历每一种情况，所以上面是01背包，如果上面用完全背包，就相当于取重了27 if (j >= k * weight[i])28 dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);29 }30 }31 printf("%d\n", dp[money]);32 }33 return 0;34 }
多重背包之 HDU -1171Big Event in HDU &HDU -2191悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。