首页 > 代码库 > TYVJ1096

TYVJ1096

2024-07-19 06:42:11   218人阅读

也不知道属于什么DP，反正就是DP算了。。
设dp[i][j]表示前i个数组合成j的最多方案数和恰好装满的01背包类似
一开始的思路是dp[i][j]=dp[i-1][j-a[i]]+1;真不知道当时是怎么能想出这个方程来的，或许是看到长得不错就要它了吧。。
后来敲代码，怎么调都对不了，后来就反思，老觉得少点东西，
原来它在这里：对于dp[i][j]来说，有两种从i-1的转移过来的方式 ：
一种是组合中没有a[i]的，即由前i-1个数组成j,dp[i-1][j] 另一种是组合中包含a[i]的(虽说包含，但是这种组合的方案数可能为0)，即由前i-1个数组成j-a[i]的方案数转移过来

状态方程：
|dp[i-1][j] j<a[i]
dp[i][j] = |
|dp[i-1][j]+dp[i-1][j-a[i]] j>=a[i]

边界条件：（根据个人的思考方式来理解来找边界）因为是根据i一层一层的向上推所以i最小的时候的那一层需要求出，这也很简单i=1时只有dp[1][a[1]]=1;别的都是0 另外会出现dp[i-1][j-a[i]],这里的j-a[i]可能为0所以需要把竖着的边界也求出，这个也很好求，不管前几个数都不可能组合出0，所以dp[i][0] = 1;(i>=1)

今天五题的最后一个了，终于完了，该睡了。。。。啊喔啊喔~~

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 10005; 7 int a[105],dp[101][maxn]; 8 int main() 9 {10     int n,m;11     while(cin>>n>>m)12     {13         for(int i = 1;i<=n;++i)scanf("%d",a+i);14         //sort(a+1,a+1+n);15         memset(dp,0,sizeof(dp));16         dp[1][a[1]] = 1;17         for(int i = 1;i<=n;++i)dp[i][0] = 1;18         for(int i = 2;i<=n;++i)19             for(int j = 1;j<=m;++j)20                 if(j>=a[i])dp[i][j] = dp[i-1][j]+dp[i-1][j-a[i]];21                 else dp[i][j] = dp[i-1][j];22 //        for(int i = 1;i<=n;++i)23 //        {24 //            for(int j = 1;j<=n;++j)25 //                printf("%d ",dp[i][j]);26 //            printf("\n");27 //        }28         printf("%d\n",dp[n][m]);29     }30     return 0;31 }

 

TYVJ1096


联系
我们