hdu 2126 Buy the souvenirs 【输出方案数】【01背包】（经典）

题目链接：https://vjudge.net/contest/103424#problem/K

转载于：https://blog.csdn.net/acm_davidcn/article/details/5549933

题目大意：

给n个物品，和m块钱，输出能够购买最多物品的个数和购买这么多物品的方案数。

解题分析：

背包的一种进化版 , 除了记录最多能买多少个 , 需要记录买这么多个的方法 , 所以要在二维的基础上加多一维 .

状态转移方程如下 : f[i][j][k]=f[i-1][j-t[i]][k-1]+f[i-1][j][k];

( 前 i 个物品在有 j 元的时候买 k 个物品的方法 ,t[i] 为第 i 个物品的价格 )

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

int val[], dp[][][];                      //dp[i][j][k]表示有k块钱，在前i种物品买j个物品的数量

int main() {

    int i, j, k, t, n, m, sign;

    scanf("%d", &t);

    while (t--) {

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

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

            scanf("%d", &val[i]);

        memset(dp, , sizeof(dp));

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

            for (k = ; k <= m; k++)

                dp[i][][k] = ;                          //初始化，一样不买种类是1

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

            for (j = ; j <= i; j++)

                for (k = m; k >= ; k--) {

                    if (k >= val[i])

                        dp[i][j][k] += dp[i - ][j - ][k - val[i]] + dp[i - ][j][k];     //加上买和不买的情况

                }

        }

        sign = ;

        for (i = n; i >= ; i--) {

            if (dp[n][i][m] != ) {          //找购买方案数不为0的最大购买数量i

                printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[n][i][m], i);

                sign = ;

                break;

            }

        }

        if (!sign)

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

    }

    return ;

}

第二种方法，对上述代码进行优化

dp[i][j][0]表示前i个物品有j元时的最多物品数，dp[i][j][1]用来储存方案数

***设当前所选的物品为i
1. 若选了物品i后，能买的件数比不选物品i的件数大，即dp[j - val[i]]>dp[j]
那么更新dp[j]，同时，dp[j][1]的方案数即为dp[j - val[i]][1]
原因是：假设dp[j - val[i]]的方案数为 AB AC 两种，那么在此情况下加个D，为ABD, ACD，仍为两种，所以dp[j] = f[j - val[i]]即可
当然，要注意dp[j - val[i]]为0的情况，因此当它为0时，dp[j] = 1，1即为D

2. 若选了物品i后，能买的件数比不选物品i的件数相同，即dp[j - val[i]] == dp[j]
即原先不选第i个物品，所需要的方案数为dp[j]；而选了物品i的方案数为dp[j - val[i]]。
因此，总的方案数即为dp[j] + dp[j - val[i]]
当然，这里也要注意dp[j - val[i]] = 0的情况，当它为0时，dp[j] += 1，1即为D

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define mem(p,k) memset(p,k,sizeof(p))

using namespace std;

int p[], dp[][];          //dp[i][j][0]表示前i个物品，最多有j元，能买多少种物品

int main() {                     //dp[i][j][1]表示前i个物品，最多有j元，能买最多物品的方案数

    int t, cur = ;

    cin >> t;

    while (t--) {

        int m, n;

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

        for (int i = ; i <= n; i++)scanf("%d", p + i);

        mem(dp, );

        for (int i = ; i <= m; i++)dp[i][] = ;              //初始化，钱数为j，一个物品都不买的方案数为1（因为此时对应的dp[i][0]=0，表示一个物品都没买）

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

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

                if (dp[j][] == dp[j - p[i]][] + ) {         //若选了物品i后，能买的件数比不选物品i的件数相同

                    if (!dp[j - p[i]][])dp[j][] += ;

                    else

                        dp[j][] += dp[j - p[i]][];

                }

                else if(dp[j][]<dp[j - p[i]][] + ) {        //若选了物品i后，能买的件数比不选物品i的件数大

                    dp[j][] = dp[j - p[i]][] + ;

                    if (!dp[j - p[i]][])dp[j][] = ;

                    else

                        dp[j][] = dp[j - p[i]][];

                }

            }

        }

        if (dp[m][]) {

            printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[m][], dp[m][]);

        }

        else printf("Sorry, you can't buy anything.\n");

    }

}

2018-05-21

巴特西

hdu 2126 Buy the souvenirs 【输出方案数】【01背包】（经典）

最新文章

热门文章