薯券使用问题

[编程题]薯券使用问题

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

某小红薯在小红书的活动中抽奖中了一定价值的薯券，这些薯券可以用来购买一批商品，求有多少种购买组合。其中一件商品可以买多件。

输入:薯券金额、商品分别价格

输出 :组合数

输入描述:

输入薯券金额、商品分别价格
例如：10 [2,3,5]
10与[2,3,5]中间有空格

输出描述:

输出4，则结果集可以为:2,2,2,2,2；5,5；2,3,5；2,2,3,3共有4种组合

示例1

输入

10 [2,3,5]

输出

算法知识视频讲解

Java

v无风

解题思路: 动态规划/背包问题
定义数组dp[i][j]表示金额为j的情况下，对于前i种商品，最多可以有多少种组合。
初始状态：
dp[...][0] = 1表示在金额为0的情况下，无论有几种商品，只能有一种组合，那就是什么都不取这一种。
状态转移：
如果不选择当前第i个商品，组合数 dp[i-1][j]
如果选择当前第i个商品，组合数 dp[i][j-v[i-1]]

得出状态转移方程:
dp[i][j] = dp[i-1][j] + dp[i][j-v[i]] (v[i]表示商品的最大金额)

解释: dp[2][10] = dp[1][10] + dp[2][10-5] = 2 + 2 = 4

	0	2	3	4	5	6	7	8	9	10
2	1	1	0	1	0	1	0	1	0	1
2,3	1	1	1	1	1	2	1	2	1	2
2,3,5	1	1	1	1	2	2	2	3	3	4

//代码如下
import java.util.*;
public class Main {
    public int solution(int a[],int v){
        int dp[][] = new int[a.length][v+1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0]=1;
            for (int j = 1; j < dp[i].length; j++) {
                if(i==0){
                    if(j<a[i]){
                        dp[i][j]=0;
                    }else {
                        dp[i][j]=dp[i][j-a[i]];
                    }
                }else {
                    if(j<a[i]){
                        dp[i][j]=dp[i-1][j];
                    }else {
                        dp[i][j]=dp[i-1][j]+dp[i][j-a[i]];
                    }
                }
            }
        }
        return dp[dp.length-1][v];
    }
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] s1 = s.split(" ");
        int v = Integer.parseInt(s1[0]);
        String[] s2 = s1[1].substring(1,s1[1].length()-1).split(",");
        int[] a = new int[s2.length];
        for (int i = 0; i < a.length; i++) {
            a[i] = Integer.parseInt(s2[i]);
        }
        System.out.println(new Main().solution(a, v));
    }
}

编辑于 2020-10-04 00:24:34 回复(0)