HDU 3449:Consumer(有依赖关系的背包)

前端之家收集整理的这篇文章主要介绍了HDU 3449:Consumer(有依赖关系的背包)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3449


题目翻译:

有N个盒子,每个盒子价值是p,其内部有m个物品,每个物品的花费为c,价值为p.

如果想要购买盒子内的物品,就必须先花钱买盒子。


所以对于某个盒子来所,我们分为买与不买,首先我们备份其没买时候的值,

然后考虑买这个盒子,如果买盒子的话,则先减去买盒子的钱。然后对m个

物品进行0,1背包,跑完之后和原备份数组中的值比较,看看是买这个盒子

获得的钱多还是不买获得的钱多。


这个是有依赖关系的背包。



AC代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

int N,W;    ///盒子数和钱数
int dp[100010];
int temp[100010];
int cost[52],value[52];
int main() {
    while(~scanf("%d%d",&N,&W)) {
        memset(dp,sizeof(dp));
        memset(temp,sizeof(temp));
        for(int i = 1; i <= N; i++) {
            int p,m;
            scanf("%d%d",&p,&m);   ///这个盒子是p元钱,里面有m件物品
            for(int j = 1; j <= m; j++) {
                scanf("%d%d",&cost[j],&value[j]);
            }
            ///要买第i箱东西。需要先买第i个箱子
            for(int j = p; j <= W; j++) {
                dp[j] = temp[j-p];
            }
            for(int j = 1; j <= m; j++) {
                for(int k = W; k >=cost[j]+p; k--) {
                    dp[k] = max(dp[k],dp[k-cost[j]] + value[j]);
                }
            }
            for(int j = 0; j <= W; j++) {
                temp[j] = max(dp[j],temp[j]);
            }
        }
        printf("%d\n",temp[W]);
    }
    return 0;
}
原文链接:https://www.f2er.com/javaschema/282472.html

猜你在找的设计模式相关文章