牛牛的超市

[编程题]牛牛的超市

热度指数：1579 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

定义一种新货币，有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个。现在你有 x(x<=100) 元，但是你想将 x 元换成若干零钱，请问有多少种换钱的方案？

示例1

输入

2,10,[[1, 5],[ 2, 4]]

输出

说明

10元可以由 2张1元的和4张2元的组成，也可以由4张1元的和3张2元的组成

备注:

x可以不属于n种币值之一

算法知识视频讲解

恍恍惚惚2018

class Solution {
public:
    int solve(int n, int x, vector<vector<int> >& a) {
        int dp[n+1][x+1];
        for(int i =0;i<=n;++i){
            for(int j=0;j<=x;++j)
                dp[i][j]=0;
        }
        dp[0][0]=1;
        for(int i=1; i<=n;++i){
            for(int j=0;j<=x;++j){
                for(int k=0;k<=a[i-1][1];++k){
                    if(dp[i-1][j]>0 && j+k*a[i-1][0]<=x)
                        dp[i][j+k*a[i-1][0]]+=dp[i-1][j];
                }
            }
        }
        return dp[n][x];
    }
};

上面是c++，下面是python

class Solution:
    def solve(self , n , x , a ):
        dp=[[0 for i in range(x+1)] for j in range(n+1)]
        dp[0][0]=1
        for i in range(1,n+1):
            for j in range(x+1):
                for k in range(a[i-1][1]+1):
                    if dp[i-1][j]>0 and j+k*a[i-1][0]<=x:
                        dp[i][j+k*a[i-1][0]]+=dp[i-1][j]
        return dp[n][x]

发表于 2020-06-10 17:14:38 回复(0)

哦咧

int solve(int n, int x, vector<vector<int> >& a) {
        int f[101]={1};
        for(int i=0;i<n;i++)
        {
            int money=a[i][0];
            for(int j=x;j>=1;j--)
            {
                for(int k=1;k<=a[i][1];k++)
                {
                    if(j<money*k) break;
                    f[j]+=f[j-money*k];
                }
            }
        }
        return f[x];
    }

牢记动态规划的阶段、状态和决策。

此外由于正推会影响一维数组之前的状态，所以我们选择逆推。

发表于 2020-07-29 09:55:03 回复(0)

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型vector<vector<>> ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    int solve(int n, int x, vector<vector<int> >& a) {
        int dp[n+1][x+1];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i=0;i<n;i++)
            for(int j=0;j<=x;j++)
                for(int k=0;k<=a[i][1];k++)
                    if(j+k*a[i][0] <= x)
                        dp[i+1][j+k*a[i][0]] += dp[i][j];
        return dp[n][x];
    }
};

发表于 2020-06-24 00:21:48 回复(0)

牛客641976621号

这是经典的多重背包问题，

class Solution:
    def solve(self, n, x, a):
    # 定义状态、开数组、同时定义了res[0]=1的边界条件
        res = [1] + [0] * x    
        # 开始循环、储值、注意数组越界问题  
        for i in range(n):
            for j in range(x, -1, -1):
                for k in range(1, a[i][1] + 1):
                    if j + k * a[i][0] > x&nbs***bsp;res[j] == 0: break
                    res[j + k * a[i][0]] += res[j]
        return res[x]

编辑于 2020-08-19 20:42:40 回复(0)

wwhhyy

这个问题就是一个动态规划的问题，可以采用二维的DP数组，给出的题解都是二维的DP，但是也可以类比于背包问题，优化成一维的DP。思路如下：

建立res数组，表示0到x的钱数。res初始值即res[0]=1，其他都为0。代表了在不使用任何硬币情况下的组成方法。

接下来开始循环，由于采用某一枚硬币之后，都是在上一时刻的基础上进行加减。故参考背包问题的一维优化，从后往前进行循环。因为如果使用硬币的话，金额一定是增加的，从后往前循环就不会对之前的造成影响。而从前往后就会改表上一时刻的值。

class Solution:
    def solve(self , n , x , a ):
        # write code here
        res = [0]*(x+1)
        res[0] = 1
        for value,nums in a:
            for idx in range(len(res)-1,-1,-1):
                if res[idx]!=0:
                    for j in range(nums):
                        now = idx+(j+1)*value
                        if now >= len(res):
                            break
                        res[now] += res[idx]
        return res[-1]

发表于 2020-07-28 16:02:59 回复(0)