Solutions CS101

Appearance

20089: NBA门票 ​

dp, http://cs101.openjudge.cn/practice/20089/

六月，巨佬甲正在加州进行暑研工作。恰逢湖人和某东部球队进NBA总决赛的对决。而同为球迷的老板大发慈悲给了甲若干美元的经费，让甲同学用于购买球票。然而由于球市火爆，球票数量也有限。共有七种档次的球票（对应价格分别为50 100 250 500 1000 2500 5000美元）而同学甲购票时这七种票也还分别剩余（n1，n2，n3，n4，n5，n6，n7张）。现由于甲同学与同伴关系恶劣。而老板又要求甲同学必须将所有经费恰好花完，请给出同学甲可买的最少的球票数X。

输入

第一行老板所发的经费N,其中50≤N≤1000000。

第二行输入n1-n7，分别为七种票的剩余量，用空格隔开

输出

假若余票不足或者有余额，则输出’Fail’

而假定能刚好花完，则输出同学甲所购买的最少的票数X。

样例输入

Sample1 Input：
5500
3 3 3 3 3 3 3 

Sample1 Output：
2

样例输出

Sample2 Input：
125050
1 2 3 1 2 5 20

Smaple2 Output：
Fail

来源: cs101-2019 龚世棋

python
# 蒋子轩23工学院
# 多重背包中的最优解问题
n = int(input())
if n % 50 != 0:
    print('Fail')
    exit()
n //= 50
nums = list(map(int, input().split()))
price = [1, 2, 5, 10, 20, 50, 100]
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(7):
#for i in range(6, -1, -1):
    cur_price = price[i]
    cur_num = nums[i]
    k = 1
    while cur_num > 0:  #二进制分组优化，时间缩短了将近两个数量级。
      									#相同物品避免重复工作，「二进制分组」提高效率。
        use_num = min(cur_num, k)
        cur_num -= use_num
        for j in range(n, cur_price * use_num - 1, -1):
            dp[j] = min(dp[j], dp[j - cur_price * use_num] + use_num)
        k *= 2
if dp[-1] == float('inf'):
    print('Fail')
else:
    print(dp[-1])

同上面几乎一样代码，如果不二进制优化，pypy可以过，python超时。

python
# 蒋子轩23工学院
# 多重背包中的最优解问题
n = int(input())
if n % 50 != 0:
    print('Fail')
    exit()
n //= 50
nums = list(map(int, input().split()))
price = [1, 2, 5, 10, 20, 50, 100]
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(6, -1, -1):
    cur = price[i]
    for k in range(n, cur-1, -1):
        for j in range(1, nums[i]+1):
            if k >= cur*j:
                dp[k] = min(dp[k], dp[k-cur*j] + j)
            else:
                break
if dp[-1] == float('inf'):
    print('Fail')
else:
    print(dp[-1])

2023/12/24，现在能说的是：NBA门票那题，题解的方法不适用于一般情况；在本题是否正确还有待验证，有正确的可能，但是感觉证明只能来讨论，会比较麻烦。

因此有了新题目，27441:NBA门票价格变了，http://cs101.openjudge.cn/practice/27441/ 下面代码没有找到找解。

python
# 2200015481, 陈涛
n=int(input())
tickets=list(map(int,input().split()))
price=[50,100,250,500,1000,2500,5000]
dp={0:0}
path={0:[0,0,0,0,0,0,0]}
for i in range(n):
    if i in dp:
        for k in range(7):
            if path[i][k]<tickets[k]:
                if i+price[k] in dp:
                    if dp[i]+1<dp[i+price[k]]:
                        dp[i+price[k]]=dp[i]+1
                        path[i+price[k]]=path[i][:]
                        path[i+price[k]][k]+=1
                else:
                    dp[i+price[k]]=dp[i]+1
                    path[i+price[k]]=path[i][:]
                    path[i+price[k]][k]+=1
if n in dp:
    print(dp[n])
else:
    print('Fail')

greedy解法有问题。例如：

10500 0 0 0 0 3 1 2

应该是10500=1∗5000+1∗2500+3∗1000，但是下面程序输出Fail

python
# 
def dfs(money, loc):
    if money == 0:
        return 0

    for i, cnt in enumerate(barrel[loc:], loc):
        n = min(cnt, money // price[i])
        if n == 0:
            continue

        result = dfs(money - n * price[i], i + 1)
        if result != "Fail":
            return n + result

    return "Fail"


N = int(input())
if N % 50:
    print("Fail")
else:
    N //= 50
    barrel = [int(i) for i in input().split()]
    price = [100, 50, 20, 10, 5, 2, 1]
    barrel.reverse()
    print(dfs(N, 0))

greedy紧急修复版本，还是不对。例如：

10500 10 0 0 0 3 1 2

python
def dfs(money, loc):
    if money == 0:
        return 0
    for i, cnt in enumerate(barrel[loc:], loc):
        n_max = min(cnt, money//price[i])
        if n_max == 0:
            continue
        for n in range(n_max, 0, -1):
            if (a := dfs(money - n*price[i], i+1)) != "Fail":
                return n + a
    return "Fail"

N = int(input())
if N % 50:
    print("Fail")
else:
    N //= 50
    barrel = [int(i) for i in input().split()]
    price = [100,50,20,10,5,2,1]
    barrel.reverse()
    print(dfs(N, 0))
python
# 23n2300010763, 胡睿诚
cost = [1,2,5,10,20,50,100]

from functools import lru_cache


@lru_cache(maxsize=None)
def dfs(money,rest):
    l = len(rest)
    t = cost[l-1]
    if l == 1:
        if money % t == 0 and money <= t * rest[0]:
            return money // t
        return 100000
    new_rest = tuple(rest[i] for i in range(l-1))
    limit = min(rest[l-1],money//t)
    return min(dfs(money-j*t,new_rest)+j for j in range(limit,-1,-1))


N = int(input())
if N % 50 != 0:
    print('Fail')
else:
    N = N // 50
    info = tuple(map(int,input().split()))
    k = dfs(N,info)
    if k == 100000:
        print('Fail')
    else:
        print(k)
python
# 2300011031, 黄源森
def changeMaking():
    n = int(input())
    if n % 50 != 0:
        print('Fail')
        return
    else:
        n = n // 50

    t = list(map(int, input().split()))
    l = [1, 2, 5, 10, 20, 50, 100]
    dp = {0: 0}

    for i in range(6, -1, -1):
        next_dp = {}
        for key in dp:
            for j in range(t[i] + 1):
                if key + j * l[i] > n:
                    break
                if key + j * l[i] in next_dp:
                    next_dp[key + j * l[i]] = min(next_dp[key + j * l[i]], dp[key] + j)
                else:
                    next_dp[key + j * l[i]] = dp[key] + j
        for u in next_dp:
            if u in dp:
                dp[u] = min(dp[u], next_dp[u])
            else:
                dp[u] = next_dp[u]

    try:
        print(dp[n])
    except:
        print('Fail')

changeMaking()
python
# gpt4 translated version of the C++ code
'''
This code should address the Runtime Error. Major adjustments include:

Input for the nti array is corrected to handle Python's 0-based index and to 
allow for proper input splitting and mapping into integers.
We create a copy of the nti list in the Anss objects before altering them, 
avoiding direct mutation of list elements that could lead to unexpected results.
When calculating the minimum index, get_min now returns the index within 
the tmp list rather than the num attribute, which allows us to properly 
identify and use the best temporary Anss object.
'''
class Anss:
    def __init__(self):
        self.n = int(1e9)
        self.num = 0
        self.nti = [0] * 8  # Python uses 0-based indexing.

def alter(n):
    return {1: 1, 2: 2, 5: 3, 10: 4, 20: 5, 50: 6, 100: 7}.get(n, -1)

def get_min(tmp):
    if not tmp:
        return -1
    ans_index = 0
    for i in range(1, len(tmp)):
        if tmp[ans_index].n > tmp[i].n:
            ans_index = i
    return ans_index

q = int(input())
if q % 50 != 0:
    print("Fail")
else:
    q //= 50
    ans = [Anss() for _ in range(q + 1)]
    ans[0].nti = [0] + list(map(int, input().split()))
    ans[0].n = 0
    ans[0].num = 0
    for i in range(1, q + 1):
        tmp = []
        for j in (1, 2, 5, 10, 20, 50, 100):
            if i - j >= 0 and ans[i - j].nti[alter(j)] > 0:
                new_anss = Anss()
                new_anss.n = ans[i - j].n
                new_anss.num = ans[i - j].num
                new_anss.nti = ans[i - j].nti.copy()
                new_anss.nti[alter(j)] -= 1
                new_anss.n += 1
                tmp.append(new_anss)
        min_index = get_min(tmp)
        if min_index == -1:
            ans[i].num = i
        else:
            ans[i] = tmp[min_index]
            ans[i].num = i

    if ans[q].n > 1e8:
        print("Fail")
    else:
        print(ans[q].n)

C++

c++
#include<cstdio>
#include<vector>
int q,n[8];
struct anss
{
	int n=1e9,num,nti[8]={0,0,0,0,0,0,0,0};//1 2 5 10 20 50 100 num==下标 
}ans[21000];
std::vector<anss> tmp;
int min()
{
	if (tmp.size()==0) return -1;
	int ans=0;
	for(int i=1;i<tmp.size();i++)
	if (tmp[ans].n>tmp[i].n) ans=i;
	return tmp[ans].num;
}
int alter(int n)
{
	if (n==1) return 1; 
	if (n==2) return 2;
	if (n==5) return 3;
	if (n==10) return 4;
	if (n==20) return 5;
	if (n==50) return 6;
	if (n==100) return 7;
	return -1;
}
int main()
{
	scanf("%d",&q);

	if (q%50!=0)
	{
		printf("Fail");
		return 0;
	}
	else q/=50;
	for(int i=1;i<=7;i++) scanf("%d",&ans[0].nti[i]);
	ans[0].n=0;
	ans[0].num=0;
	for(int i=1;i<=q;i++)
	{
		if(i-1>=0 && ans[i-1].nti[1]>0) tmp.push_back(ans[i-1]);
		if(i-2>=0 && ans[i-2].nti[2]>0) tmp.push_back(ans[i-2]);
		if(i-5>=0 && ans[i-5].nti[3]>0) tmp.push_back(ans[i-5]);
		if(i-10>=0 && ans[i-10].nti[4]>0) tmp.push_back(ans[i-10]);
		if(i-20>=0 && ans[i-20].nti[5]>0) tmp.push_back(ans[i-20]);
		if(i-50>=0 && ans[i-50].nti[6]>0) tmp.push_back(ans[i-50]);
		if(i-100>=0 && ans[i-100].nti[7]>0)	tmp.push_back(ans[i-100]);
		int best=min();
		if (best==-1)
		{
			ans[i].num=i;
		}
		else
		{
			ans[i]=ans[best];
			ans[i].num=i;
			ans[i].n++;
			ans[i].nti[alter(i-best)]--;
		}
		tmp.clear();
	}
	if (ans[q].n>1e8) printf("Fail");
	else printf("%d",ans[q].n);
}