qq_39530477
CYMWN
采纳率100%
2018-06-17 14:43 阅读 1.4k
已采纳

动态规划问题求解思路

10

动态规划题目:请问这道问题的各阶段确定状态变量如何确定?请各位大神指教!
假设工人人数为 x,有 y 项任务(其中:1 <= y,x <= 100),假定每个任务的工作量都是一样的,要求每个工人至少完成一项任务,同时还要求每项任务至少要被完成一次,问有多少种安排方案?当然也有可能没有一种方案存在。
(附测试数据:x=4 ,y=2时,结果为7

                    x=15 ,y=12,结果为106470
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

5条回答 默认 最新

  • 已采纳
    weixin_42325834 书香门第 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; 
    }
    
    点赞 评论 复制链接分享
  • caozhy 从今以后生命中的每一秒都属于我爱的人 2018-06-17 15:13
  • qq_42246737 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
    .......

    点赞 评论 复制链接分享
  • m0_37599363 无情的我 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 khk_abc 2018-06-18 05:54

相关推荐