代金券组合

var price=parseInt(readline());
var scdLine=readline().split(' ');
var types=scdLine[0];
var coupons=scdLne.slice(1).map(Number);

function couponNum(price){
    var flag=false;
    coupons.sort();
    var result=0;
    
    function calc(curPrice){
        if(!curPrice||coupons[0]>curPrice){
        console.log('Impossible');
        return;
    }
    for(var i=types-1; i>=0; i--){
        var cur=coupons[i];
        if(flag){return};
        if(cur>curPrice){
            continue;
        }
        result+=Math.floor(curPrice/cur);
        if(curPrice%cur){
            calc(curPrice%cur);
        }else{flag=true}
      }
    }
    
    console.log(result);
    return result;
}

while(true){
    let nums = parseInt(readline())
    if(nums === 0 ) break
    let coins = readline().split(" ").map(Number).slice(1)
    console.log(fn(coins,nums))
}
function fn(coins,nums){
    let dp = new Array(nums+1).fill(Infinity)
    dp[0] = 0
    for(let i = 1;i<=nums;i++){
        for(let coin of coins){
            if( i >= coin ){
                dp[i] = Math.min(dp[i],dp[i-coin]+1)
            }
        }
    }
    return dp[nums] === Infinity ? 'Impossible' : dp[nums]
}

JavaScript 2020美团-代金券组合😎dp
leet322 今天0308的每日一题

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line', line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr[inArr.length-1]==0){
        for (let i = 0; i < inArr.length-2; i+=2) {
            let amount = +inArr[i]
            let coins = inArr[i+1].split(' ').map(e=>+e)
            console.log(coinChange(coins, amount))
            
        }
    }
})

var coinChange = function(coins, amount) {
    let dp = new Array(amount+1).fill(Infinity)
    dp[0] = 0
    for (let coin of coins ) {
      for (let i = 1; i <= amount; i++) {
        if (i - coin >= 0) {
          dp[i] = Math.min(dp[i], dp[i - coin] + 1)
        }
      }
    }
    return dp[amount] === Infinity ? 'Impossible' : dp[amount]
  }

// 只通过50%..
function mysort(a,b){
    if(a<b){
        return 1;
    }else if(a>b){
        return -1
    }else{
        return 0;
    }
}
while(true){
    var salary=parseInt(readline())
    if(salary==0){
        break;
    }
    var arr=readline().split(' ').map(Number)
    var n=arr[0]
    // 最小次数
    var min=10000;
    // 是否能满足条件的标识
    var flag=false;
    // 有个问题，输入的数组需要先排序。。并且从大到小
    arr=arr.slice(1).sort(mysort)
    for(var i=0;i<arr.length;i++){
        var inmin=0;
        if(salary>=arr[i]){
            if(salary==arr[i]){
                inmin=1;
                break;
            }
            var tem=Math.floor(salary/arr[i]);
            // 剩下的额度
            var a=salary-arr[i]*tem;
            inmin=tem;
            for(var j=i+1;j<arr.length;j++){
                if(a>=arr[j]){
                    var b=Math.floor(a/arr[j]);
                    inmin+=b;
                    a=a-b*arr[j]
                    if(a==0){
                        flag=true;
                        min=inmin<min?inmin:min;
                        break;
                    }
                }
            }
        }
    }
    print(flag?min:'Impossible')
}

function fn(num, coinStr){
   let coinArr = coinStr.split(' ').map(Number).slice(1);
   let fnArr = [];
   fnArr[0] = 0;
   for(let i = 1; i<= num; i++){
       for(let c = 0; c<coinArr.length; c++){
            if(coinArr[c] <= i){
               fnArr[i] = Math.min(fnArr[i] || Infinity, fnArr[i-coinArr[c]]+1) || Infinity
            }
       }
   }
   return fnArr[num] === Infinity ? 'Impossible' : fnArr[num];
}

console.log(fn(10,'4 50 30 20 5'))

res = float('inf')
def DFS(num,i,r,target):
    global res
    if target == 0:
        res = min(res,r)
        return
    if target < 0:
        return
    if i >= len(num):
        return
    cur = target // num[i]
    j = cur
    while j >= 0:
        if r + j >= res:
            return
        else:
            DFS(num,i+1,r+j, target-num[i] * j)
            j -= 1
            
while True:
    target = int(input().strip())
    if target == 0:
        break
    num = list(map(int,input().strip().split()))
    num = sorted(num,reverse=True)
    res = float('inf')
    DFS(num,0,0,target)
    if res == float('inf'):
        print('Impossible')
    else:
        print(res)

import sys
class Solution:
    def func(self, price, num, arr):
        arr.sort()
        if arr[0] > price:
            return "Impossible"
        dp = [0 for _ in range(price+1)]
        dp[0] = 0
        for i in range(1, arr[0]):
            dp[i] = "Impossible"
        dp[arr[0]] = 1
        for i in range(arr[0]+1, price+1):
            dp[i] = float('inf')
            for opt in arr:
                if i-opt < 0:
                    break
                if i-opt == 0:
                    dp[i] = 1
                if dp[i-opt] == "Impossible":
                    continue
                dp[i] = min(dp[i], dp[i-opt] + dp[opt])
            if dp[i] == float('inf'):
                dp[i] = "Impossible"
        return dp[price]
                     
if __name__ == '__main__':
    solution = Solution()
    while True:
        price = int(sys.stdin.readline().strip())
        if price == 0:
            break
        arr = list(map(int, sys.stdin.readline().strip().split()))
        num = arr.pop(0)
        print(solution.func(price, num, arr))

//java代码
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {//可以用来判断是否有下一个整数
            int n = in.nextInt();
                        if(n == 0) break;
            if (in.hasNextInt()) {//如果还有下一个数，可以将其放入变量x中
                int x = in.nextInt();
                int arr[] = new int[x + 1];
                for (int i = 0; i < x; i++) {
                    arr[i] = in.nextInt();
                }
                int dp[] = new int[n + 1];
                Arrays.fill(dp, n + 1);
                dp[0] = 0;
                for (int i = 1; i <= n; i++) {
                    for (int j = 0; j < x; j++) {
                        if (arr[j] <= i) dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
                    }
                }
                System.out.println(dp[n] > n ? "Impossible" : dp[n]);
            }

        }
    }
}

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line', line => {
    if (!line) return
    inArr.push(line.trim())
    if (parseInt(inArr[inArr.length - 1]) == 0) {
        //collect amount and coin
        let amount = parseInt(inArr[0]);
        let coins = inArr[1].split(' ').map(Number);
        console.log(coinChange(amount, coins));

    }
})
function coinChange(amount, coins) {
    const dp = new Array(amount + 1).fill(Infinity)
    dp[0] = 0
    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (i >= coins[j]) {
                dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i])
            }
        }
    }
    return dp[amount] == Infinity ? "Impossible" : dp[amount]
}

#include <iostream>
using namespace std;
int n,m,dp[100001],temp,a[20];
int main(){
	while(cin>>n){
		for(int i=0;i<=100000;i++){
			dp[i]=-1;
		}
		if(n==0){
			break;
		}
		cin>>m;
		for(int i=0;i<m;i++){
			cin>>temp;
			a[i]=temp;
			if(temp<=n){
				dp[temp]=1;
			}
		}
		for(int i=0;i<=n;i++){
			for(int j=0;j<m;j++){
				if(a[j]<i&&dp[i-a[j]]!=-1){
					if(dp[i]==-1){
						dp[i]=dp[i-a[j]]+1;
					}
					else{
						dp[i]=min(dp[i],dp[i-a[j]]+1);
					}
					
				}
			}
		}
		if(dp[n]==-1){
			cout<<"Impossible"<<endl;
		}
		else{
			cout<<dp[n]<<endl;
		}
		
	}
	return 0;
}