posts - 33,  comments - 33,  trackbacks - 0

整数划分问题是把一个正整数 N 拆分成一组数,并且使这组数相加等于 N 的问题.
比如:
6
5 + 1
4 + 2, 4 + 1 + 1
3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

这里,5+1和1+5是同一种分法。
这里探讨整数划分的可行解的数目。
问题求解:
首先假设正整数n拆分成k个数(不允许有0),用f(n,k)表示正整数n拆分成k个数的可行拆分种类的数目。
那么
f(n,n)表示n拆分成n个数(即只有n个1),显然f(n,n) = 1
然后,可以按照这k份中是否有一份的数为1分成两类:
1)   这k份中没有1份含1的:那么可以在n中拿出k个"1"出来,分到k份中,再将剩下n-k分到k份中,于是这时有
f(n,k) = f(n-k,k)
2)  这k份中至少有一份含有1:首先在n中拿1个"1"出来,再将剩下n-1分到k-1份中,于是这时有:f(n,k) = f(n-1,k-1)

综合起来就是:
f(n,n) = 1
f(n,k) = f(n-k,k) + f(n-1,k-1)
这两个递归式可以使用动态规划求解。

题目链接:
http://poj.org/problem?id=1283
题解:直接按照整数划分来解
代码:
import java.util.Scanner;
import java.util.Arrays;;

public class Main 
{
    
private static long [][]dp = new long[205][205];
    
    
private static long Test(int _n,int _k)
    
{
        
if(_n < _k)
            
return 0;
        
for(int i = 0; i <= _n; ++i)
            Arrays.fill(dp[i],
0);
        
        
for(int i = 1; i <= _n; ++i)
        
{
            dp[i][i] 
= 1;
        }

        
        
for(int i = 2; i <= _n; ++i)
        
{
            
for(int j = 1; j <= _k; ++j)
            
{
                dp[i][j] 
= dp[i-1][j-1];
                
if(i - j > 0)
                    dp[i][j] 
+= dp[i-j][j];
            }

        }

        
        
return dp[_n][_k];
    }

    
    
public static void main(String[] args) 
    
{
        
int n,k;
        Scanner in 
= new Scanner(System.in);
        n 
= in.nextInt();
        k 
= in.nextInt();
        
while(!(n == 0 &&  k == 0))
        
{
            System.out.println(Test(n,k));
            n 
= in.nextInt();
            k 
= in.nextInt();
        }


    }


}


 
http://poj.org/problem?id=1664
题解:这题允许存在空盘,怎么做呢?换一种思路,我们先给每个盘子放上一个"1",那么当这个盘子为1时,表示为空,于是答案便是f(n+m,n)

代码:
import java.util.Scanner;
import java.util.Arrays;

public class Main 
{
    
private static long [][]dp = new long[32][32];
    
    
private static long Test(int _n,int _k)
    
{
        
if(_n < _k)
            
return 0;
        
for(int i = 0; i <= _n; ++i)
            Arrays.fill(dp[i],
0);
        
        
for(int i = 1; i <= _n; ++i)
        
{
            dp[i][i] 
= 1;
        }

        
        
for(int i = 2; i <= _n; ++i)
        
{
            
for(int j = 1; j <= _k; ++j)
            
{
                dp[i][j] 
= dp[i-1][j-1];
                
if(i - j > 0)
                    dp[i][j] 
+= dp[i-j][j];
            }

        }

        
        
return dp[_n][_k];
    }

    
    
public static void main(String[] args) 
    
{
        Scanner in 
= new Scanner(System.in);
        
int testcase = in.nextInt();
        
int m,n;
        
for(int i =0; i < testcase; ++i)
        
{
            m 
= in.nextInt();
            n 
= in.nextInt();
            System.out.println(Test(m
+n,n));
        }

    }

}


posted on 2011-03-28 18:42 bennycen 阅读(1149) 评论(1)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理