hdu2126（求方案数的01背包）

时间：2023-03-08 16:45:50

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

题意： n个物品，m元钱，每个物品最多买一次，问最多可以买几件物品，并且输出方案数。

分析：一看就想到01背包，不过得加一维来表示能买的物品件数。dp[i][j]表示在i元内至多能买j件物品。则状态转移方程为：dp[i][j]+=dp[i-a[k][j-1].

最后把在1~m元内买到的最大件数mx加起来就是题目所求。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <stack>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 1000000007

#define inf 0x3f3f3f3f

#define N 1000010

#define clr(a) (memset(a,0,sizeof(a)))

using namespace std;

int dp[][],a[];

int n,m;

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)scanf("%d",&a[i]);

        clr(dp);

        dp[][]=;

        int mx=;

        for(int i=;i<=n;i++)

        for(int j=m;j>=a[i];j--)

        {

            for(int k=n-;k>=;k--)

            {

                if(dp[j-a[i]][k])dp[j][k+]+=dp[j-a[i]][k],mx=max(mx,k+);

            }

        }

        if(mx==)

        {

            puts("Sorry, you can't buy anything.");

            continue;

        }

        int ans=;

        for(int i=;i<=m;i++)ans+=dp[i][mx];

        printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",ans,mx);

    }

}

相关文章