hdu 3449 Consumer 有依赖的01背包

发布时间：2020-12-13 22:35:45 所属栏目：百科来源：网络整理

导读：Description FJ is going to do some shopping,and before that,he needs some boxes to carry the different kinds of stuff he is going to buy. Each box is assigned to carry some specific kinds of stuff (that is to say,if he is going to buy one

Description

FJ is going to do some shopping,and before that,he needs some boxes to carry the different kinds of stuff he is going to buy. Each box is assigned to carry some specific kinds of stuff (that is to say,if he is going to buy one of these stuff,he has to buy the box beforehand). Each kind of stuff has its own value. Now FJ only has an amount of W dollars for shopping,he intends to get the highest value with the money.

Input

The first line will contain two integers,n (the number of boxes 1 <= n <= 50),w (the amount of money FJ has,1 <= w <= 100000) Then n lines follow. Each line contains the following number pi (the price of the ith box 1<=pi<=1000),mi (1<=mi<=10 the number goods ith box can carry),and mi pairs of numbers,the price cj (1<=cj<=100),the value vj(1<=vj<=1000000)

Output

For each test case,output the maximum value FJ can get

Sample Input

       
       
        
         3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60

Sample Output

210

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
int dp[100][100010];
int main()
{
    int n,money;
    int box,m;
    int w,p;
    while(~scanf("%d %d",&n,&money))
    {
        memset(dp[0],sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            scanf("%d %d",&box,&m);
            for(int j=0; j<box; j++)//这里肯定买不到
                dp[i][j]=-1;
            for(int j=box; j<=money; j++)//这里就是选择i时先用上从的取得的价值-盒子的花费
                dp[i][j]=dp[i-1][j-box];
            for(int j=0; j<m; j++)    //这里就是用01背包进行更新本层取得的价值
            {
                scanf("%d %d",&w,&p);
                for(int k=money; k>=w; k--)
                    if(dp[i][k-w]!=-1)
                        dp[i][k]=max(dp[i][k],dp[i][k-w]+p);
            }
            for(int j=0; j<=money; j++)//这里更新是因为不是每次求的得就是最大的因为它是在减去篮子钱的基础上和本层的比较
                dp[i][j]=max(dp[i-1][j],dp[i][j]);
        }
        printf("%dn",dp[n][money]);
    }
    return 0;
}

滚动数组优化，内存减少了接近40倍给跪了--->>> 点击打开链接

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
int dp[100010];
int tem[100010];
int main()
{
    int n,&money))
    {
        memset(dp,&m);
            memcpy(tem,dp,sizeof(dp));
            /*for(int j=box; j<=money; j++)//这里就是选择i时先用上从的取得的价值-盒子的花费
                dp[i][j]=dp[i-1][j-box];*/
            for(int j=0; j<m; j++)    //这里就是用01背包进行更新本层取得的价值
            {
                scanf("%d %d",&p);
                for(int k=money-box; k>=w; k--)

                        tem[k]=max(tem[k],tem[k-w]+p);
            }
            for(int j=box; j<=money; j++)//这里更新是因为不是每次求的得就是最大的因为它是在减去篮子钱的基础上和本层的比较
                dp[j]=max(dp[j],tem[j-box]);
        }
        printf("%dn",dp[money]);
    }
    return 0;
}

下面写了一个错误的，特比注意有依赖的背包要考虑很多情况

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
int dp[100][100010];
int main()
{
    int n,&m);
            for(int j=0; j<box; j++)//这里肯定买不到
                dp[i][j]=-INF;
            /*for(int j=box; j<=money; j++)//这里就是选择i时先用上从的取得的价值-盒子的花费
                dp[i][j]=dp[i-1][j-box];*/
            for(int j=0; j<m; j++)    //这里就是用01背包进行更新本层取得的价值
            {
                scanf("%d %d",&p);
                for(int k=money; k>=w; k--)
                        dp[i][k]=max(dp[i][k],dp[i-1][k-w-money]+p);
            }
            /*for(int j=0; j<=money; j++)//这里更新是因为不是每次求的得就是最大的因为它是在减去篮子钱的基础上和本层的比较
                dp[i][j]=max(dp[i-1][j],dp[i][j]);*/
        }
        printf("%dn",dp[n][money]);
    }
    return 0;
}
//这种情况我本来想忽略最后的比较但是忘了一个很重要的问题那就是如果不比较那么开始的杀死后全部赋值为-INF那么这个地方就影院不会更新

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!