欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【Lintcode】1448. Card Game

程序员文章站 2022-07-08 10:52:13
题目地址:https://www.lintcode.com/problem/card-game/description给定nnn个物品,其价值为数组AAA,成本为数组BBB,问在给定总预算ccc和最小总价值ppp的情况下,有多少个组合可以使得总成本是小于ccc,并且总价值是大于ppp的。题目保证每个物品的价值和成本都是非负的(注意,这里可以是000)。答案模109+710^9+7109+7后返回。思路是动态规划。设f[i][j][k]f[i][j][k]f[i][j][k]是前iii个物品(从000开...

题目地址:

https://www.lintcode.com/problem/card-game/description

给定 n n n个物品,其价值为数组 A A A,成本为数组 B B B,问在给定总预算 c c c和最小总价值 p p p的情况下,有多少个组合可以使得总成本是小于 c c c,并且总价值是大于 p p p的。题目保证每个物品的价值和成本都是非负的(注意,这里可以是 0 0 0)。答案模 1 0 9 + 7 10^9+7 109+7后返回。

思路是动态规划。设 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]是前 i i i个物品(从 0 0 0开始计数),总价值大于等于 j j j并且成本恰好等于 k k k的方案数。那么根据第 i i i个物品是否选,可以分为两种情况,如果不选,那么方案数就是 f [ i − 1 ] [ j ] [ k ] f[i-1][j][k] f[i1][j][k];如果选,那么方案数就是 f [ i − 1 ] [ max ⁡ { 0 , j − A [ i ] } ] [ k − B [ i ] ] f[i-1][\max\{0,j-A[i]\}][k-B[i]] f[i1][max{0,jA[i]}][kB[i]],所以就有: f [ i ] [ j ] [ k ] = f [ i − 1 ] [ j ] [ k ] + f [ i − 1 ] [ max ⁡ { 0 , j − A [ i ] } ] [ k − B [ i ] ] f[i][j][k]=f[i-1][j][k]+f[i-1][\max\{0,j-A[i]\}][k-B[i]] f[i][j][k]=f[i1][j][k]+f[i1][max{0,jA[i]}][kB[i]]边界条件,考虑第 0 0 0个物品是否选。如果不选,则 f [ 0 ] [ 0 ] [ 0 ] = 1 f[0][0][0]=1 f[0][0][0]=1,别的 f [ 0 ] [ . > 0 ] [ 0 ] = 0 f[0][.>0][0]=0 f[0][.>0][0]=0;如果选,则 f [ 0 ] [ . ≤ A [ 0 ] ] [ B [ i ] ] = 1 f[0][.\le A[0]][B[i]]=1 f[0][.A[0]][B[i]]=1,所以算 f [ 0 ] f[0] f[0]的时候,要将两种情况加总。代码如下:

public class Solution {
    /**
     * @param n:           The number of cards
     * @param totalProfit: The totalProfit
     * @param totalCost:   The totalCost
     * @param a:           The profit of cards
     * @param b:           The cost of cards
     * @return: Return the number of legal plan
     */
    public int numOfPlan(int n, int totalProfit, int totalCost, int[] a, int[] b) {
        // Write your code here
        int MOD = (int) (1E9 + 7);
        
        // dp[i][j][k]是从前i + 1个物品里选,价值大于等于j的且成本恰好等于k的组合总数
        int[][][] dp = new int[n][totalProfit + 2][totalCost];
        
        // 如果第0个物品不选
        dp[0][0][0] = 1;
        for (int i = 0; i <= Math.min(a[0], totalProfit + 1); i++) {
        	// 这里要注意b[0] = 0的情况,所以要写成 += 1
            dp[0][i][b[0]] += 1;
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= totalProfit + 1; j++) {
                for (int k = 0; k < totalCost; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (k >= b[i]) {
                        dp[i][j][k] += dp[i - 1][Math.max(0, j - a[i])][k - b[i]];
                    }
                    
                    dp[i][j][k] %= MOD;
                }
            }
        }
        
        int res = 0;
        for (int i = 0; i < totalCost; i++) {
            res += dp[n - 1][totalProfit + 1][i];
            res %= MOD;
        }
        
        return res;
    }
}

时空复杂度 O ( n p c ) O(npc) O(npc)

可以用滚动数组优化。代码如下:

public class Solution {
    /**
     * @param n:           The number of cards
     * @param totalProfit: The totalProfit
     * @param totalCost:   The totalCost
     * @param a:           The profit of cards
     * @param b:           The cost of cards
     * @return: Return the number of legal plan
     */
    public int numOfPlan(int n, int totalProfit, int totalCost, int[] a, int[] b) {
        // Write your code here
        int MOD = (int) (1E9 + 7);
        // dp[i][j][k]是从前i + 1个物品里选,价值大于等于j的且成本恰好等于k的组合总数
        int[][][] dp = new int[2][totalProfit + 2][totalCost];
        
        dp[0][0][0] = 1;
        for (int i = 0; i <= Math.min(a[0], totalProfit + 1); i++) {
            dp[0][i][b[0]] += 1;
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= totalProfit + 1; j++) {
                for (int k = 0; k < totalCost; k++) {
                    dp[i & 1][j][k] = dp[i - 1 & 1][j][k];
                    if (k >= b[i]) {
                        dp[i & 1][j][k] += dp[i - 1 & 1][Math.max(0, j - a[i])][k - b[i]];
                    }
                    
                    dp[i & 1][j][k] %= MOD;
                }
            }
        }
        
        int res = 0;
		for (int i = 0; i < totalCost; i++) {
            res += dp[n - 1 & 1][totalProfit + 1][i];
            res %= MOD;
        }        

        return res;
    }
}

时间复杂度不变,空间 O ( p c ) O(pc) O(pc)

本文地址:https://blog.csdn.net/qq_46105170/article/details/110121972