正文

hdu_2079_(01背包)(dfs)

Jason333  Jason333  2022-08-22  264

关键词：

选课时间(题目已修改,注意读题)

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4478 Accepted Submission(s): 3480

Problem Description

又到了选课的时间了，xhd看着选课表发呆，为了想让下一学期好过点，他想知道学n个学分共有多少组合。你来帮帮他吧。（xhd认为一样学分的课没区别）

Input

输入数据的第一行是一个数据T，表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40)，k(1 <= k <= 8)。
接着有k行，每行有两个整数a(1 <= a <= 8),b(1 <= b <= 10)，表示学分为a的课有b门。

Output

对于每组输入数据，输出一个整数，表示学n个学分的组合数。

Sample Input

2 2

1 2

2 1

40 8

1 1

2 2

3 2

4 2

5 8

6 9

7 6

8 8

Sample Output

445

最开始用多重背包做，发现二进制优化多出的零头可能发生重复，但是没相处解决方案。

看题解用的01背包，稍作修改避免了重复。

因为数据规模小，用dfs也很方便。

01背包：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int cost[10],num[10],dp[45],n;

void zero_one(int cost,int num)
{
    for(int j=n;j>=cost;j--)
        for(int k=1;k<=num&&j-k*cost>=0;k++)
            dp[j]+=dp[j-cost*k];
}


int main()
{
    int t,k;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        scanf("%d%d",&n,&k);
        for(int i=0;i<k;i++)
        {
            scanf("%d%d",&cost[i],&num[i]);
            if(cost[i]*num[i]>n)
                num[i]=n/cost[i];
            //dp[cost[i]]=1;
        }
        for(int i=0;i<k;i++)
        {
            zero_one(cost[i],num[i]);
        }
        printf("%d
",dp[n]);
    }
    return 0;
}

dfs：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int cost[10],num[10],res,n,k;

void dfs(int index,int sum)
{
    if(index>k||sum>n)
        return;
    if(index==k&&sum!=n)
        return;
    if(sum==n)
    {
        res++;
        return;
    }
    for(int i=0;i<=num[index];i++)
    {
        dfs(index+1,sum+i*cost[index]);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        res=0;
        scanf("%d%d",&n,&k);
        for(int i=0;i<k;i++)
            scanf("%d%d",&cost[i],&num[i]);
        dfs(0,0);
        printf("%d
",res);
    }
    return 0;
}

hdu1171_bigeventinhdu01背包

BigEventinHDUTimeLimit:10000/5000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):24321 AcceptedSubmission(s):8562ProblemDescriptionNowadays,weallknowthatC 查看详情

hdu1864_最大报销额(背包/01背包)

解题报告题目传送门#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#defineinf99999999usingnamespacestd;intv,w[35],d[4],dw1,sum,dp[31*1000*100];intmain(){doubleQ,dw; 查看详情

hdu1864_简单01背包

/*题目大意：一堆数，找到一个最大的和满足这个和不超过Q，题目链接要学会分析复杂度！*/#include<cstdio>#include<cstring>#defineMAX(a,b)(a>b?a:b)constintN=3000050;intdp[N],data[N];floatbound;intn,cnt;intmain(){chartype;floatprice 查看详情

hdu_3591_(多重背包+完全背包)

ThetroubleofXiaoqianTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):2006 AcceptedSubmission(s):712ProblemDescri 查看详情

hdu_2191_多重背包

http://acm.hdu.edu.cn/showproblem.php?pid=2191 简单多重背包题。 #include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intn,m,p[105],h[105],c[105],ans[105];intmain(){ 查看详情

hdu_2955(代码片段)

...DP练习题，自己的水平有限，参考了网上其他的答案。01背包问题，如何选择背包容量和物品的价值在这里是比较困难的地方，把银行的钱当做背包，把概率当做价值，总容量为所有银行的总钱数，求不超过被抓概率的情况下，... 查看详情

hdu_3732_(多重背包)

AhuiWritesWordTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):2915 AcceptedSubmission(s):1036ProblemDescription 查看详情

hdu_3496_(二维费用背包)

WatchTheMovieTimeLimit:3000/1000MS(Java/Others) MemoryLimit:65535/65535K(Java/Others)TotalSubmission(s):7585 AcceptedSubmission(s):2427ProblemDescriptionN 查看详情

hdu_1175_dfs

http://acm.hdu.edu.cn/showproblem.php?pid=1175 dfs(x,y,i,num)，xy表示位置，i表示方向，num表示转向次数，num=2时候的剪枝很重要。 #include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;int 查看详情

hdu_1455_dfs

http://acm.hdu.edu.cn/showproblem.php?pid=1455 intdfs(intall,intsum,intnow)，all代表剩余总长，sum，代表每段长，now代表当前拼接的长度。if(a[i]+now==sum||now==0)return0;while(a[i+1]==a[i])i++;这两句话剪枝很重要。 #include<io 查看详情

hdu_5094_dfs

http://acm.hdu.edu.cn/showproblem.php?pid=5094 bfs,vis[x][y][z]，z表示钥匙的状态，用二进制来表示，key[x][y]储存当前位置钥匙的二进制表示。注意起始点有钥匙的情况。 #include<iostream>#include<cstdio>#include<string>#inc 查看详情

hdu_1142(最短路+dfs)

Jimmyexperiencesalotofstressatworkthesedays,especiallysincehisaccidentmadeworkingdifficult.Torelaxafterahardday,helikestowalkhome.Tomakethingsevennicer,hisofficeisononesideofaforest,andhishouseisonthe 查看详情

01背包

<spanstyle="color:#3333ff;">/*__________________________________________________________________________________________________*copyright:GrantYuan**algorithm:01背包**time:2014.7.18**__ 查看详情

hdu344801背包+dfs

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=3448Description0/1bagproblemshouldsoundfamiliartoeverybody.Everyearthmanknowsitwell.Hereisamutant:giventhecapacityofabag,thatistosay,thenumberofgoo 查看详情

动态规划_01背包_完全背包_多重背包_分组背包(代码片段)

目录动态规划问题结题思路：模板题链接：01背包思路：代码：完全背包思路:代码多重背包思路：代码：组合背包思路：代码：动态规划问题结题思路：模板题链接：01背包模板题完全背包... 查看详情

hdu_5692_dfs序+线段树

http://acm.hdu.edu.cn/showproblem.php?pid=5692 这道题真的是看了题解还搞了一天，把每条路径后序遍历按1-n重新标号，储存每个点在哪些路径中出现过（l和r数组），然后转化成线段树来更新和取最大值。注意，如果使用递归建线段树... 查看详情

（经典dfs）hdu_1241oildeposits(代码片段)

HDU_1241OilDeposits ProblemDescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangularregionoflandatatime,andcreatesagridthatdividesthelandintonumeroussquareplots.Itthenanalyzeseachplotseparately,usingsensingequipmenttode... 查看详情

2079acm选课时间背包或母函数(代码片段)

...种组合数，注意同样学分，课程没有区别思路：两种方法背包母函数背包：注意初始化时dp[0]=1,其他都为0，循环时从学分N开始更新，减到为0，表示成功，组合数加一。代码：#include<iostream>usingnamespacestd;intmain()int 查看详情