动态规划题目：请问这道问题的各阶段确定状态变量如何确定？请各位大神指教！
假设工人人数为 x，有 y 项任务(其中：1 <= y,x <= 100)，假定每个任务的工作量都是一样的，要求每个工人至少完成一项任务，同时还要求每项任务至少要被完成一次，问有多少种安排方案？当然也有可能没有一种方案存在。
（附测试数据：x=4 ,y=2时，结果为7
x=15 ,y=12,结果为106470
浏览 1.4k
已采纳
动态规划问题求解思路
- 点赞
- 写回答
- 关注问题
- 收藏
- 分享
- 邀请回答
微信扫一扫5条回答 默认 最新
- 书香门第 2018-06-18 05:29已采纳
思路如下：
题目的要求本质上是说有x个人，分成y组，要求每组至少有个一个人。问有多少种分法。
动态数组为dp[x][y]。表示x个人分成y组有多少种分法。有题目要求所知，
对所有x，dp[x][1] = 1，dp[x][y] = 1，如果x < y，则dp[x][y] = 0.否则，
dp[x][y] = dp[x-1][y] * y + dp[x-1][y-1]，也就是说，状态[x,y]肯定可以从二种相邻状态得到，
第一种，x-1个人已经组成了y组，则第x个人可以放入任意一组中，也就是有dp[x-1][y]_*y种可能；
第二种，x-1个人已经组成了y-1组，则第x个人必须被放到第yzu中，也就是有dp[x-1][y-1]种可能。
对于x-1个人组成了y-2甚至更少组的情况，不可能在多一个人情况下组成y组，可以不予考虑。c++程序如下：_const int INF = 110; int dp[INF][INF]; void buildDP() { for (int i = 1; i < INF; i++) { dp[i][1] = 1; dp[i][i] = 1; } for (int i = 2; i < INF; i++) { for (int j = 2; j < i; j++) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * j; } } } int main() { int x, y; cin >> x >> y; buildDP(); cout << dp[x][y] << endl; return 0; }点赞 打赏 评论分享 - qq_42246737 2018-06-18 01:27
x为人数，y 为任务数。
x>0并且x y>0并且<100;
那这数大了。至少做一种任务，。又没有任务工作量 ，如果 是99种任务，且只有一个人，如果 按你所说也可以一个人做99个任务。
1*99
2*99
......
99*99
同时又任务也可多次完成
1*99*99
.......点赞 打赏 评论分享 - 无情的我 2018-06-18 04:24
不知道对不对
import java.util.Scanner;public class A {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[][] C = new int[n+1][m+1];
if (n < m) {
return;
}
for (int i = 0; i <= m; i++) {
C[i][i] = 1;
}
for(int i=0;i<=n;i++){
C[i][1] = 1;
}for (int j = 2; j <= m; j++) { for (int i = j+1; i <= n; i++) { for (int k = 0; k <= i - j; k++) { C[i][j]+=C[i-k-1][j-1]*Cnm(i-1,k); } } } System.out.println(C[n][m]); } public static int Cnm(int n, int m) { if(n==m || m==0){ return 1; } int res = 1; for (int i = 0; i < m; i++) { res *= (n - i); } for (int i = 1; i <= m; i++) { res /= i; } return res; }}
点赞 打赏 评论分享 - khk_abc 2018-06-18 05:54