例一:
给出N台电脑和K辆卡车,要求每辆卡车至少放一台电脑。问共有多少种放法运走这些电脑?
数据范围N (1<=N<=200) and K(1<=K<=N)。
[输入输出]:
输入的每一行是空格隔开的电脑数n和卡车数k ,输出对应的运法总数。
[样例]:
Sample Input
1 1
7 3
0 0
Sample Output
1
4
[解题分析]:
分析:典型dp,状态转移方程dp[i][j]=dp[i-1][j-1]+dp[i][j-i];
dp[i][j]表示i辆卡车装j台电脑的方法数。
例如:8台电脑3台车
import java.util.*;
public class Main{
private long dp[][]=new long[201][201];
public Main(){
init();
}
private void init(){
for(int i=1;i<201;i++)
{
dp[i][i]=dp[1][i]=dp[i][0]=dp[0][i]=1;
}
for(int i=2;i<201;i++)
{
for(int j=i+1;j<201;j++)
{
dp[i][j]=dp[i-1][j-1]+dp[i][j-i];
}
}
}
public long dp(int k,int n){
return dp[k][n];
}
public static void main(String args[]){
Scanner in=new Scanner(System.in);
Main m=new Main();
while(true){
int n=in.nextInt();
int k=in.nextInt();
if(n==0 && k==0) break;
System.out.println(m.dp(k,n));
}
}
}
例二 最小邮票数
题目描述:
有若干张邮票,要求从中选取最少的邮票张数凑成一个给定的总值。
如,有1分,3分,3分,3分,4分五张邮票,要求凑成10分,则使用3张邮票:3分、3分、4分即可。
输入:
有多组数据,对于每组数据,首先是要求凑成的邮票总值M,M<100。然后是一个数N,N〈20,表示有N张邮票。接下来是N个正整数,分别表示这N张邮票的面值,且以升序排列。
输出:
对于每组数据,能够凑成总值M的最少邮票张数。若无解,输出0。
样例输入:
10
5
1 3 3 3 4
样例输出:
3
import java.util.Scanner;
public class Main{
static int INF=Integer.MAX_VALUE;
public static void main(String args[]) {
Scanner in=new Scanner(System.in);
while(true) {
int m=in.nextInt();
int n=in.nextInt();
int[] w=new int[n];
int[] dp=new int[m+1];
for(int i=0;i<n;++i) w[i]=in.nextInt();
for(int i=1;i <= m; ++i) dp[i] = INF;//dp[i]表示凑成总值为i时所需的的最小邮票张数
dp[0]=0;
for(int i=0;i<n;++i) {
// System.out.println("i==================="+i);
for(int j = m;j>=w[i];--j) {
if(dp[j-w[i]] == INF) continue;
else{
dp[j]=Math.min(dp[j],dp[j-w[i]]+1);
// System.out.println("dp["+j+"]="+dp[j]);
}
}
}
if(dp[m] == INF) System.out.println("0");
else
System.out.printf("%d\n", dp[m]);
}
}
}
- 大小: 45 KB
分享到:
相关推荐
标题 "动态规划算法学习十例之八" 暗示了我们将探讨动态规划这一重要的算法概念,特别是通过一个具体的例子——Matrix Chain Multiplication(矩阵链乘法)来深入理解。动态规划是一种解决复杂问题的有效方法,它...
在这个“动态规划算法学习十例之七”的主题中,我们将聚焦于一个具体的动态规划问题——最长公共子序列(Longest Common Subsequence,简称LCS)。这个问题在计算机科学中具有很高的实用价值,尤其是在比较和分析...
在这个“动态规划算法学习十例之九”的主题中,我们将聚焦于如何通过DP来解决实际问题。尽管描述部分没有提供具体的实例,但从标题来看,我们可以推测这是一个关于动态规划应用的系列教程的第九个例子。 动态规划的...
在这个主题“动态规划算法学习十例之六”中,我们将探讨如何利用动态规划方法来解决实际问题。博文链接虽然未提供具体内容,但我们可以根据提供的文件名推测讨论的是一个具体的编程实例。 `Main.java`通常是一个...
标题中的“动态规划算法学习十例之五”表明这篇内容主要关注的是计算机科学中的动态规划算法,这是一种在解决复杂问题时非常有效的优化方法。动态规划通常用于处理具有重叠子问题和最优子结构的问题,通过将大问题...
在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...
在这个"动态规划算法学习十例之二"中,我们很可能会探讨两个具体的动态规划应用:一个可能涉及二项式系数计算,另一个可能是斐波那契数列的求解。下面,我们将深入这两个主题,理解它们背后的动态规划策略。 首先,...
在这个“动态规划算法学习十例之一”的主题中,我们将会探讨动态规划的基本概念和一个具体的实例,通过分析`Test.java`源码来深入理解。 首先,动态规划的核心思想是将一个大问题分解为相互重叠的小问题,并通过...
三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的主题。下面将对这三个方面进行详细的...
在压缩包中的"近似串匹配问题"文件可能包含了这样的C语言实现,可以作为学习和理解近似串匹配动态规划算法的一个实例。 总结一下,近似串匹配的动态规划算法是一种高效的方法,通过Levenshtein距离或Hamming距离...
在课程设计过程中,学生还将学习如何分析动态规划算法的时间复杂度和空间复杂度。例如,大多数动态规划解决方案的时间复杂度为O(n*W),其中n是物品数量,W是背包容量,而空间复杂度通常是O(n*W)或者更优,取决于是否...
标题中提到的是“算法参考资料国际大学生程序设计竞赛例题解3 图论·动态规划算法·综合题专集”。这份资料集中的标题揭示了内容的几个关键点,即它是一份专门为解决算法问题而编写的参考资料,特别针对国际大学生...
在实际编程中,理解和掌握动态规划算法对于提高问题解决能力至关重要,因为它能够优雅地处理复杂度高且具有结构重叠的优化问题。在学习动态规划时,推荐阅读如《Introduction to Algorithms》等经典教材,它们深入浅...
动态规划算法以其卓越的能力,成为应对这类问题的首选工具。它通过把复杂问题分解成更小、更易于管理的子问题,以递归的方式进行解决。这种方法不仅效率高,而且在很多情况下比其他算法(如贪婪算法或分治算法)更优...
**算法动态规划专题** 动态规划(Dynamic Programming,简称DP)是一种在计算机科学中解决最优化问题的算法技术,尤其在解决复杂度较高的多阶段决策问题时表现得尤为出色。它通过将大问题分解为小问题,并存储子...
动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...
"基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf" 本文研究主要集中在基于岭回归机器学习算法的项目成本预测研究,以A风景园林规划研究院规划设计项目为例。该研究的目的...
本资源包含的100例算法涵盖了排序、搜索、图论、动态规划、递归等多个重要类别。 1. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。排序算法是数据处理的基础,用于将一组无序的...