1
zhangbw_
C++ 完全背包问题 将总人数n + 1当作背包容量，套餐的人数作为每件物品重量 注意可以有余票，如20人可以买30张票(如果这30张票价格更优的话) 最终答案为dp[n + 1]「购买 n + 1张票的最小花费」 #include
using namespace std;
int main() {
int n, m, k, weight[1005], price[1005];
cin >> n >> m >> k;
price[0] = k; weight[0] = 1; // 单人票，价格为k，作为物品0
for (int i = 1; i <= m; ++i) { // 添加m种套餐(物品)
cin >> price[i] >> weight[i];
}
int dp[n + 2]; memset(dp, 0x3f, sizeof(dp));
dp[0] = 0; // dp[i]: 购买i张票的最小花费
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n + 1; ++j) {
if (j >= weight[i]) dp[j] = min(dp[j], dp[j - weight[i]] + price[i]);
else dp[j] = min(dp[j], price[i]); // 重点
}
}
cout << dp[n + 1] << endl;
return 0;
}
编辑于 2022-08-19 22:11:05
回复(0)
1
JavaScript
w布响丸辣
/*世界杯门票
这个题可以看做是一个背包问题，人的个数相当于背包的容量，票的价格相当于价值，dp[i]表示买到i张票时的最小花费为dp[i]，最后dp[n]即为买到n张票时的最小花费
*/
var line1 = readline().split(' ');
var n = parseInt(line1[0]),
m = parseInt(line1[1]),
k = parseInt(line1[2]);
n++;
var dp = [];
for(var i=0;i<=n;i++){ dp[i] = i*k;
}
for(var i=0;i var line2 = readline().split(' '); for(var j=1;j<=n;j++){ if(j-line2[1]>=0){ dp[j] = Math.min(dp[j],dp[j-line2[1]]+parseInt(line2[0])); }else{ dp[j] = Math.min(dp[j],parseInt(line2[0])); } } } print(dp[n]); 发表于 2018-09-17 16:20:14 回复(0) 1 Java 求天求地求Offer //基本思路：刚开始不整理，就是将买几张票的钱数先存在dp中，等套餐，单买的情况都存好后， //整理dp[]，整理的话有两种情况：①当前的票数要花的最少的钱数等于小于当前票数的最小钱的情况 //之和（因为小于当前票数的最少的钱已经整理好），②等于大于当前票数花的钱和当前的最小数 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int ticket[]=new int[1001];//表示买i张票所需要的最少的钱 int m=sc.nextInt(); int k=sc.nextInt(); for(int i=0;i<1001;i++){ ticket[i]=i*k; } for(int i=0;i int mm=sc.nextInt(); int t=sc.nextInt(); ticket[t]=Math.min(ticket[t],mm); } for(int i=1;i<=n+1;i++){ int min=ticket[i]; for(int j=1;j<=1000;j++){ if(j min=Math.min(min,ticket[j]+ticket[i-j]); else min=Math.min(min,ticket[j]); } ticket[i]=min; } System.out.println(ticket[n+1]); } } 发表于 2018-07-03 22:50:28 回复(0) 1 桃符 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner s = new Scanner(System.in); // 人数数量 int n = s.nextInt(); // 套餐数量 int m = s.nextInt(); // 单价 int k = s.nextInt(); // 定义票的数组 int[][] tickets = new int[m + 1][2]; // 遍历获得套餐信息（价钱x，人数y） for (int i = 1; i <= m; i++) { int x = s.nextInt(); int y = s.nextInt(); tickets[i][0] = x; tickets[i][1] = y; } tickets[0][0] = k; tickets[0][1] = 1; //【套餐】【背包容量（人数）】 int[][] dp = new int[m+1][n+2]; for(int i = 1;i<=m;i++){ dp[i][0] = 0; } for(int j = 0;j<=n+1;j++){ dp[0][j] = j* k; } // 线性规划(套餐->人数)，完全背包，将人数作为容量 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n + 1; j++) { if(j 发表于 2018-06-30 13:27:19 回复(1) 1 昵称已被占用、 写出暴力递归，再改写成动动态规划，未进行任何优化。 /** * * 思路： * 遍历每种套餐组合，每种套餐均可购买 0 ~ 当前缺少门票/当前套餐提供的票数 （向上取整），最后所得门票大于需求 或者 到达数组尾部 时返回。。 * * ps： * 单买门票等价于票数为1的套餐。 * * @author Yanjie * */ public class BuyTicket { public static void main(String[] args) throws Exception { Scanner in = new Scanner(new FileInputStream("F:\\java\\JavaLearning\\src\\nowcoder\\praticetest\\BuyTicakets.txt")); int n = in.nextInt(); int m = in.nextInt(); int k = in.nextInt(); // 套餐数组，dp[][0]:价格，dp[][1]:票数 int[][] pacakges = new int[m + 1][2]; pacakges[0][0] = k; pacakges[0][1] = 1; for (int i = 1; i <= m; i++) { pacakges[i][0] = in.nextInt(); pacakges[i][1] = in.nextInt(); } System.out.println(process1(pacakges, n, 0, 0)); System.out.println(process2(pacakges, n)); } /** * 暴力递归 * * @author Yanjie * * @param pacakges * @param n * @param curIndex * @param curTickets * @return */ public static int process1(int[][] pacakges, int n, int curIndex, int curTickets) { // base case if (curTickets >= n + 1) { // 票数已够 return 0; } if (curIndex == pacakges.length) { // 票数未够但已无可用套餐，该方案不满足条件，废弃。 return -1; } int minMoney = (n + 1) * pacakges[0][0]; int curMaxNum = (int) Math.ceil( (double) ((n + 1) - curTickets) / pacakges[curIndex][1] ); // 向上取整，即可以多买票。 for (int k = 0; k <= curMaxNum; k++) { int money = process1(pacakges, n, curIndex + 1, curTickets + k * pacakges[curIndex][1]); if (money == -1) { continue; } else { money += pacakges[curIndex][0] * k; // money = 当前套餐花费 + 后续套餐花费 } minMoney = Math.min(minMoney, money); } return minMoney; } /** * 动态规划 * * @author Yanjie * * @param pacakges * @param n * @return */ public static int process2(int[][] pacakges, int n) { // dp int[][] dp = new int[pacakges.length + 1][n + 2]; // base case for (int j = 0; j <= n + 1; j++) { dp[pacakges.length][j] = -1; } // 普通位置 for (int i = pacakges.length - 1; i >= 0; i--) { for (int j = n; j >= 0; j--) { int minMoney = (n + 1) * pacakges[0][0]; int curMaxNum = (int) Math.ceil( (double) ((n + 1) - j) / pacakges[i][1] ); for (int k = 0; k <= curMaxNum; k++) { int money = 0; if (j + k * pacakges[i][1] <= n + 1) { // 数组越界处理，票数是否够数 money = dp[i + 1][j + k * pacakges[i][1]]; } if (money == -1) { continue; } else { money += pacakges[i][0] * k; } minMoney = Math.min(minMoney, money); } dp[i][j] = minMoney; } } return dp[0][0]; } } 编辑于 2018-06-27 16:19:48 回复(0) 1 海超人 #include 编辑于 2018-06-24 19:07:57 回复(0) 1 勇敢的奋进者123 //动态规划，我更喜欢使用二维数组，更容易理解 #include #include #include using namespace std; int min(int a, int b) { return (a < b) ? a :b; } int main() { int n, m, k; int x, y; while(cin >> n >> m >> k) { vector vector price[0] = k; count[0] = 1; for(int i = 1; i <= m; i++) { cin >> x >> y; price[i] = x; count[i] = y; } //定义dp[i][j]:用前i种方案凑j个人的最少费用 //最后输出dp[m][n+1]即可 vector //1.对dp[0][j]:用第0种方法去凑j个人，只能是count[0]的倍数 for(int j = 0; j <= n+1; j++) { if(j%count[0] == 0) dp[0][j] = (j/count[0])*price[0]; } //2.对dp[i][0]:用前i种方法去凑0个人，即不需要钱，全部置0 for(int i = 0; i <= m; i++) dp[i][0] = 0; //3.对dp[i][j]: for(int i = 1; i <= m; i++) for(int j = 1; j <= n+1; j++) { if(j-count[i] >= 0) dp[i][j] = min(dp[i-1][j], dp[i][j-count[i]]+price[i]); else dp[i][j] = min(dp[i-1][j], price[i]); } cout << dp[m][n+1] << endl; } return 0; } 发表于 2018-06-28 22:48:04 回复(0) 5 luckyxue 人的个数相当于背包的容量，票的价格相当于价值，dp[i]表示买到i张票时的最小花费为dp[i]，最后dp[n + 1]即为买到n + 1张票时的最小花费 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(); int m = sc.nextInt(); int k = sc.nextInt(); int[] dp = new int[n + 2]; for(int i = 1; i <= n + 1; i++) { dp[i] = i * k; } 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]); } } } 发表于 2018-06-30 01:12:31 回复(0) 0 C/C++ looker. 贪心算法（应该算这个）全部通过，但是感觉有运气成分。每种套餐按人均票价排序，优先选最便宜的套餐买，买到剩余人数小于套餐人数时，考虑下一个稍贵一点套餐，继续搜索，(但此时要考虑特殊情况，即干脆在买一个该套餐，票多就多了，记下这种方式的总钱数sum_[i];)最终价格sum_price；比较常规思路得到的sum_price与各种坑爹情况的sum_[i]的最小值，及最小钱数。 #include 发表于 2019-05-25 00:05:06 回复(1) 0 Freddien #include #include using namespace std; int y_man[1005]; int x_price[1005]; int d[1005];//费用矩阵 int main() { int n,m,k; cin>> n>> m>>k; x_price[0] = k ;y_man[0] = 1; for(int i =1 ;i<=m ;i++) cin >>x_price[i] >>y_man[i]; d[0] = 0; for(int i = 1;i<=n+1 ;i++) { d[i] = (n+1)*k; //初始化的d[1-(n+1)] } for(int i= 0;i<=m;i++) //取前m中方案 求的费用d[j] ;注意 ，一个人单独购票也是一种方案 { for(int j= 1;j<=n+1 ;j++) //更新 费用d[] 矩阵 { if(j >=y_man[i]) d[j] = min(d[j],d[j-y_man[i]]+x_price[i]); else d[j] = min(d[j],x_price[i]);//非常重要，当人数小于团体票时， //有可能出现团体票费用比其他组合还便宜 } } cout << d[n+1]; return 0; } 发表于 2019-05-16 23:01:23 回复(0) 0 孙超越a #include 发表于 2019-05-16 17:21:53 回复(0) 0 luckydog~~~ #include 发表于 2018-07-04 10:46:39 回复(0) 0 蛟龙吐火球丰 #include #include #include #include using namespace std; int cost; int k; bool com(pair { return a.first/a.second>b.first/b.second; } void core(vector { if(num>=total) { cost=min(cost,cos); return; } if(cos>cost) return; cost=min(cos+(total-num)*k,cost); for(int i=idx;i core(co,i,n,num+co[i].second,cos+co[i].first,total); } int main() { int n,m; while(cin>>n>>m>>k) { vector for(int i=0;i cin>>co[i].first>>co[i].second; sort(co.begin(),co.end(),com); cost=INT_MAX; core(co,0,m,0,0,n+1); cout< } } 发表于 2018-06-30 08:54:13 回复(0) 0 gengman //完全背包 #include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f int v[1010],w[1010]; int dp[2100]; int main() { int m,n; for(int i=0;i<=2099;i++) dp[i]=inf; scanf("%d%d%d",&n,&m,&w[0]); v[0]=1; n++; int maxx=-1; dp[0]=0; for(int i=1;i<=m;i++) { scanf("%d%d",&w[i],&v[i]); if(maxx } for(int i=0;i<=m;i++) { for(int k=0;k*v[i]<=n+maxx;k++) { for(int j=k*v[i];j<=n+maxx;j++) { dp[j]=min(dp[j],dp[j-v[i]]+w[i]); } } } int minn=inf; for(int i=n;i<=n+maxx;i++) { minn=min(dp[i],minn); } printf("%d\n",minn); } 发表于 2018-06-29 19:53:59 回复(0) 0 Java 刘禅挥泪斩孔明 public class Main { // 动态规划:dp[i]表示i个人的最小花销 public static void main(String[] args) { java.util.Scanner sc = new java.util.Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt(), i, j; int price, num, dp[] = new int[n+2];// dp[0] == 0 for (i = 1; i < n+2; ++i) dp[i] = k * i; for (i = 0; i < m; ++i) { price = sc.nextInt(); num = sc.nextInt(); for (j = 1; j < n+2; ++j) dp[j] = Math.min(dp[j], dp[Math.max(0, j-num)] + price); } System.out.println(dp[n+1]); } } 编辑于 2018-06-29 12:05:09 回复(0) 0 Python 翰墨轩lc n=input(); print n m=input(); print m k=input(); print k x=[]; y=[]; price=[]; for t in range(m): xi=input(); yi=input(); price1=(n+1)*k; price2=((n+1)/yi)*xi+(n+1)%2*k; price price.append(min(price1,price2)) result=min(price); print result 发表于 2018-06-28 20:51:42 回复(0) 0 1367356 // 本题中可能会存在 购买某一种套餐之后， 人数不够，套餐中有些票是用不着的情况。 //所以买的票数是大于人数的， 最多多买多少张票呢。 应该为m中套餐中最大票数-1。 // 例如 单独一张票 100元，但是有一种套餐是100张票，总共10元钱。 其它人都团购完成，还剩余一个人，那么剩余的一个人就应该买这种套餐。 所以最后买的票数为n+1+100-1. //然后用动态规划求解即可。 import java.util.HashMap; import java.util.*; import java.util.stream.Collectors; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); //n个小伙伴，共n+1个人 int m=scanner.nextInt(); //m中套餐 int k=scanner.nextInt(); //1张门票的价格 int[] arrm = new int[m]; Map 编辑于 2018-06-27 16:52:49 回复(0) 0 麦垛上的守望者 改了很久没过：不知道为什么？ 我自己编的几个测试数据都没问题 那个472是怎么算出来的？ 我手动检验了一下，实在凑不出来472，反倒是凑出来了644，就是 22 + 103 + 173*3 ，这三种套餐刚好凑够117张票，结果是644元钱。。。 还有一点就是，我的理解是，不能多买，用套餐凑的话，必须得凑够n+1张 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int k = in.nextInt(); int[][] data = new int[m+1][2]; for(int i=0;i long[] dp = new long[n+2]; //当总人数为i时，最少花费 for(int i=0;i=data[j][1]){// dp[i] = Math.min(dp[i], dp[i-data[j][1]]+data[j][0]); } } } System.out.println(dp[n+1]); in.close(); } } 116 26 450 230 15 531 70 777 63 589 61 266 81 322 77 517 73 820 68 241 77 103 42 256 91 750 87 866 51 569 97 524 83 173 2 22 69 653 14 846 17 896 69 111 90 194 68 326 2 335 18 175 79 933 55 472 你的输出为: 644 借用完全背包的思路，写了另一版，还是出错在这个案例上，同样是472 644 public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int k = in.nextInt(); int[][] data = new int[m + 1][2]; for (int i = 1; i < m + 1 && in.hasNextInt(); i++) { data[i][0] = in.nextInt(); data[i][1] = in.nextInt(); } // 单张买也算作一种套餐： 花费k，人数1 data[0][0] = k; data[0][1] = 1; if (n == 0) { System.out.println(k); return; } long[][] dp = new long[m+1][n+2]; // dp[i][j]表示前i个套餐，买j张票的最小花费 /*for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);*/ for(int i=0;i 编辑于 2018-06-24 12:05:38 回复(12) 0 WAK 您的代码已保存 答案错误:您提交的程序没有通过所有的测试用例 case通过率为80.00% 测试用例: 116 26 450 230 15 531 70 777 63 589 61 266 81 322 77 517 73 820 68 241 77 103 42 256 91 750 87 866 51 569 97 524 83 173 2 22 69 653 14 846 17 896 69 111 90 194 68 326 2 335 18 175 79 933 55 对应输出应该为: 472 你的输出为: 44 明明有22元69张票，而且套餐购买无限制，买117张只需要两个22元套餐，结果为什么是472？ 发表于 2018-06-23 20:38:03 回复(5)