牛牛与世界杯门票

今年的世界杯要开始啦，牛牛作为一个球迷，当然不会放过去开幕式现场的机会。但是牛牛一个人去又觉得太过寂寞，便想叫上了他的n个小伙伴陪他一起去莫斯科(一共n+1人)。当牛牛开始订开幕式的门票时，发现门票有m种套餐，每种套餐需要花费x元，包含y张门票，每张门票也可以单独购买，此时这张门票的价格为k元。请问牛牛要怎样选择购买门票，使得他花费的钱最少。(每种套餐可以购买次数没有限制)。

解答：
这个题可以看做是一个完全背包，人的个数相当于背包的容量，票的价格相当于价值，dp[i]表示买到i张票时的最小花费为dp[i]，最后dp[n]即为买到n张票时的最小花费。

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()) {int n = sc.nextInt();
​​​​​​    ​ n++;int m = sc.nextInt();int k = sc.nextInt();int[] dp = new int[n + 2];for(int i = 1; i <= n; i++) {dp[i] = i * k;//初始化dp[i],最普遍的选择}int x, y = 0;while(m-- > 0) {//对每种套餐进行选择x = sc.nextInt();y = sc.nextInt();for(int i = 1; i <= n + 1; i++) {if(i - y >= 0) {  //当当前种类套餐票数小于当前人数dp[i] = Math.min(dp[i], dp[i - y] + x);//选择普通选择与该套餐票价和剩余选择的最小值} else {//人数不够套餐数dp[i] = Math.min(dp[i], x);//选择较小的票价}}}System.out.println(dp[n + 1]);}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！