薯券使用问题

#include <iostream> #include <vector> #include <stdlib.h> #include <math.h> #include <算法>使用名称空间std；整数l = 0； vector <int> p;整数int ans = 0 ; int dg（int loc，int n）{// loc记录当前数组元素位置，n记录当前余额如果（n == 0）{ans ++;返回0;}如果（loc == 0）{if（n％p [0] == 0）ans ++;//到最小商品，可整除则ans ++返回0;}如果（n <p [0]）返回0； int temp = n;而（temp> = 0）{dg（loc-1，temp）；//进行下一轮递归temp- = p [loc];//最初的商品价格}返回0;} int main（）{cin >> num;图表而（cin >> t）{如果（t ==']'）中断； if（t-'0'<= 9 && t-'0'> = 0）{int tt = t-'0';p.push_back（tt）;l = p.size（）；sort（p.begin（），p.end（））；dg（l-1，num）;cout << ans << endl;返回0;}

与力扣 面试题 08.11. 硬币 这题一样

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();
        String[] tmp = s.substring(1, s.length() - 1).split(",");
        int[] arr = new int[n + 1];
        int[] p = new int[tmp.length];
        for(int i = 0; i < tmp.length; i++) {
            p[i] = Integer.parseInt(tmp[i]);
        }

        arr[0] = 1;

        for(int a : p) {
            for(int i = a; i < arr.length; i++) {
                arr[i] = (arr[i] + arr[i - a]);
            }
        }

        System.out.println(arr[n]);
    }

}

解题思路: 动态规划/背包问题
定义数组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

//代码如下
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));
    }
}

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int total = scanner.nextInt();
            String ret = scanner.nextLine();
            ret = ret.substring(2, ret.length() - 1);//因为读入了空格
            String[] elem = ret.split(",");

            //使用dp[i][j]  定义数组dp[i][j]表示金额为j的情况下，对于前i种商品，最多可以有多少种组合。
            //1、如果不取j商品  那么dp[i][j]=dp[i-1][j]
            //2、如果取j商品  那么dp[i][j]= dp[i]  [j-Value[i-1]]  (Value[i-1]对应此商品价格) 完全背包问题 因此是 dp[i]  [j-Value[i-1]]

            int[][] dp = new int[elem.length + 1][total+1];
            //对于 价格为0时 不买任何商品  这种组合是1
            for (int i = 0; i <= elem.length; i++) {
                dp[i][0] = 1;
            }
            for (int i = 1; i <= elem.length; i++) {//商品个数
                for (int j = 1; j <= total; j++) {//花费金额

                    if (j >= Integer.parseInt(elem[i - 1]))
                        dp[i][j] = dp[i - 1][j] + dp[i][j - Integer.parseInt(elem[i - 1])];
                    else
                        dp[i][j] = dp[i - 1][j];

                }
            }

            System.out.println(dp[elem.length][total]);
        }

package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)
 
func main() {
    inputReader := bufio.NewReader(os.Stdin)
    line, _ := inputReader.ReadString('\n')
    line = strings.Replace(line, "\n", "", -1)
    lines := strings.Split(line, " ")
    n, _ := strconv.Atoi(lines[0])
    lines[1] = lines[1][1:]
    lines[1] = lines[1][:len(lines[1])-1]
    s := strings.Split(lines[1], ",")
    nums := []int{}
    for _, c := range s {
        temp, _ := strconv.Atoi(c)
        nums = append(nums, temp)
    }
    dp := make([]int, n+1)
    dp[0] = 1
 
    for _, j := range nums {
        for i := j; i <= n; i++ {
            dp[i] += dp[i-j]
        }
    }
 
 
    fmt.Print(dp[n])
}

import java.lang.*;
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        List<Integer> prices = new ArrayList<>();
        
        String s = scanner.nextLine();
        String[] listStr = s.substring(2,s.length()-1).split(",");
        for(int i = 0;i<listStr.length;i++){
            prices.add(Integer.parseInt(listStr[i]));
        }
        
        int[] dp = new int[num+1];
        dp[0] = 1;
        for(int i = 0;i<prices.size();i++){
            for(int j = prices.get(i);j<=num;j++){
                dp[j]+=dp[j-prices.get(i)];
            }
        }
        System.out.println(dp[num]);
    }
}

class Solution:
    def Totalnumberofcombinations(self,num,lis):
        lis=sorted(lis)
        return self.back(num,lis)
    def back(self,num,lis):
        count=0  #这个初始化非常重要
        i=0
        while i<len(lis):
            if num-lis[i]>0:
                count+=self.back(num-lis[i],lis[i:])
                i+=1
            elif num-lis[i]==0:
                count+=1
                return count
            else:
                return count
        return count
ss=Solution()
str1 = input()
arr = str1.split()
num= int(arr[0])
srr=arr[1][1:len(arr[1])-1]
lis= [ int(i) for i in srr.split(",")]
res=ss.Totalnumberofcombinations(num,lis)
print(res)

data = input()
n, a = data.split()
n = eval(n)
a = eval(a)
di = {}
 
 
def go(ind, left):
    global ans
    if left < 0:
        return 0
    k = (ind, left)
    if k in di:
        return di[k]
    if ind == len(a):
        if left == 0:
            di[k] = 1
        else:
            di[k] = 0
        return di[k]
    s = 0
    for c in range(left // a[ind] + 1):
        s += go(ind + 1, left - c * a[ind])
    di[k] = s
    return s
 
 
ans = go(0, n)
ans &= (1 << 32) - 1
print(ans)

import java.util.Arrays;
import java.util.Scanner;

public class ShuJuan {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int sum = scanner.nextInt();
        String next = scanner.next();
        int length = next.length();
        String subString = next.substring(1,length-1);
        String[] split = subString.split(",");
        int[] prices = new int[split.length];
        for(int i = 0;i < split.length;i++){
            prices[i] = Integer.parseInt(split[i]);
        }
        Arrays.sort(prices);
        System.out.println(dfs(sum,prices,0,0));
    }
    private static int dfs(int totalmoney,int[] zonglei,int start,int num){
        if(totalmoney<0){
            return 0;
        }
        for(int i=start;i<zonglei.length;i++){
            if(totalmoney-zonglei[i]<=0){
                if(totalmoney-zonglei[i]==0) {
                    num+=1;
                    return num;
                }
                break;
            }
            num=dfs(totalmoney-zonglei[i],zonglei,i,num);
        }
        return num;
    }
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int> >result;
//这里location的作用是为了防止出现重复的数组
void fun2(int sum,vector<int>&data,vector<int>&temp,int location)
{
	if (sum == 0)
	{
		result.push_back(temp);
		return;
	}
	else if(sum<0)
	{
		return;
	}
	else {
		for (int i = location; i < data.size();i++ )
		{
			sum -= data[i];
			temp.push_back(data[i]);
			fun2(sum, data, temp,i);
			sum += data[i];
			temp.pop_back();
		}
	}
}
void fun1(int sum, vector<int>& data)
{

	vector<int> temp;
	for (int i = 0; i < data.size(); i++)
	{
		temp.push_back(data[i]);
		sum -= data[i];
		fun2(sum, data, temp,i);
		sum += data[i];
		temp.pop_back();
	}
	
}
int main() {
	string Stringdata;
	int n;
	//cout << "请输入总价格：" << endl;
	cin >> n;
	//cout << "请输入每个优惠券的值：类似于[2,3,5]：" << endl;
	cin >> Stringdata;
	int i = 0;
	vector<int>data;
	while (Stringdata[i] == ' ')
		i++;
	while (i < Stringdata.length())
	{
		if (Stringdata[i] != ' ' && Stringdata[i] != '[' && Stringdata[i] != ',' && Stringdata[i] != ']')
		{
			int sum = 0;
			while (Stringdata[i] != ',' && Stringdata[i] != ']')
			{
				sum *= 10;
				sum += Stringdata[i] - '0';
				i++;
			}
			data.push_back(sum);
		}
		else
		{
			i++;
		}
	}
	sort(data.begin(),data.end());
	cout << endl;
	fun1(n, data);
	cout <<"size:"<< result.size() << endl;
	for (int i = 0; i < result.size(); i++)
	{
		for (int j = 0; j < result[i].size(); j++)
		{
			cout << result[i][j];
		}
		cout << endl;
	}
}

#include <cmath>
#include <climits>
#include <sstream>
#include <iostream>
#include <map>
#include <vector>
#include <stack>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution{
    public:
    long long int solve(int sum, vector<int> prices){
        int pricesSize = prices.size();
        vector<vector<long long int>> dp(pricesSize+1, vector<long long int>(sum+1, 0));
        dp[0][0] = 1;
        for(int i = 1; i<=pricesSize; i++){
            for(int j=0; j<=sum; j++){
                for(int k=0; j + k <= sum; k+=prices[i-1]){
                    if(dp[i-1][j]>0){
                        dp[i][j+k] += dp[i-1][j];
                    }
                }
            }
        }
        return dp[pricesSize][sum];
    }
};
int main(){
    Solution a;
    int count;
    string str;
    cin >> count;
    cin >> str;
    if(str.find("[")!= string::npos){
        str=str.replace(str.find("["),1,"");
    }
    if(str.find("]")!= string::npos){
        str=str.replace(str.find("]"),1,"");
    }
    istringstream iss(str);
    vector<int> prices;
    string tmp;
    while(getline(iss, tmp, ',')){
        prices.push_back(atoi(tmp.c_str()));
    }
    cout << a.solve(count, prices) % 4294967296 << endl;
}
// 最后的徐亚哦对 4294967296(2^32) 取余

class Solution {
private: 
        vector<vector<int> >res;
        vector<int>path;
        vector<int>candidates;
public:
    void dfs(int cnt,int target)
    {
        if(target==0)
        {
            res.push_back(path);
            return;
        }
        for(int i=cnt;i<candidates.size() && target-candidates[i]>=0;i++)
        {
            path.push_back(candidates[i]);
            dfs(i,target-candidates[i]);
            path.pop_back();
        }
    }
     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
          this->candidates = candidates;
        dfs(0,target);
        return res;
    }
};