动态规划算法题求解？？？

1. 动态规划算法题求解？？？

这个问题不比用动态规划法。
1，2，4，8 ……
第n项为 2^(n-1) 的等比数列就满足这个要求。

2. 一个关于算法的问题。 应该是要用到动态规划。 答对有加分。

二维费用背包问题。
我们把n个数看做物品，把值a[i]赋予两重含义：重量和价值。即第i个物品的重量为a[i]，价值为a[i]。
设f[i][v][u]表示前i个物品中选取v个物品重量为u时的最大价值。则，状态转移方程为
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-1][u-a[i]]+a[i]}
v，u的最大容量分别是个数最大容量x，重量最大容量m。
然后就是裸的模版题了。
贴个我写的代码给你吧~
输入：第一行一个整数n。第二行n个整数，表示a[i]。第三行一个整数x。第四行一个整数m。
样例：
5
1 2 3 4 5
3
8
code：
#include    
#include 
#define maxn 102
#define maxx 102
#define maxm 102
#define oo 0x3f3f3f3f;
int main()  
{  
    int i=0,j=0,k=0;
    int n=0,m=0,x=0;
    int a[maxn],dp[maxx][maxm];
    bool s[maxn][maxx][maxm];
    while(scanf("%d",&n) != EOF)  
    {  
        for(i=0;i<n; i++)scanf("%d",&a[i]);
        scanf("%d",&x);
        scanf("%d",&m);
        memset(dp,0,sizeof(dp));
        memset(s,0,sizeof(s));
        //恰好取x个数，初始化为负无穷
        //若需要求至多x个数，则初始化为0 
        for(j=x;j>=1;--j)
            for(k=m;k>=0;k--)
                dp[j][k]=-oo;
        //DP求解 
        for(i=0;i<n;++i)
            for(j=x;j>=1;--j)
                for(k=m;k>=a[i];--k)
                    if(dp[j][k]<dp[j-1][k-a[i]]+a[i])
                    {
                        dp[j][k]=dp[j-1][k-a[i]]+a[i];
                        s[i][j][k]=true;
                    }
        //方案不存在时 
        if(dp[x][m]<0)
        {
            printf("NO SOLUTION.\n");
            continue;
        } 
        //输出方案
        printf("A POSSIBLE SOLUTION:");
        bool plus=false;
        for(i=n-1,j=x,k=m;i>=0;--i)
        {
            if(s[i][j][k])
            {
                if(plus)putchar('+');
                else plus=true;
                printf("%d",a[i]);
                --j;
                k-=a[i];
            }
        }
        //输出和 
        printf("=%d\n",dp[x][m]);
    }
    return 0;
}

3. c语言的动态规划算法的这道题怎么做啊，求大神！！！

申请二维数组 dp[N+1][M+1]。
 1. dp[0][j]，0<=j<=m，表示一种题型都不选择并且竞赛总时间为 j 时最多得分，显然等于 0。
 2. dp[i][0]，1<=i<=n，表示只选择竞赛题型 0..i-1 并且竞赛总时间为 0 时最多得分，显然等于0。
3. dp[i][j]，1<=i<=n，1<=j<=m，表示最多只选择竞赛题型 0..i-1 并且竞赛总时间为 j 时最多得分。
3.1 如果不选择第 i-1 种题型，则最多得分 dp[i][j] = dp[i-1][j]。
3.2 如果只选择 1 道第 i-1 种题型，则最多得分 dp[i][j] = 1*point[i-1] + dp[i-1][j-time[i-1]]。
3.3 如果只选择 2 道第 i-1 种题型，则最多得分 dp[i][j] = 2*point[i-1] + dp[i-1][j-2*time[i-1]]。
...
3.k+1 最多可以选择 k=j/time[i-1] 道第 i-1 种题型，则最多得分 dp[i][j] = k*point[i-1] + dp[i-1][j-k*time[i-1]]。
以上 k+1 种情况中的最大值即为 dp[i][j] 的最多得分，即 dp[i][j] = max(dp[i-1][j],  1*point[i-1] + dp[i-1][j-time[i-1]], 2*point[i-1] + dp[i-1][j-2*time[i-1]], ..., dp[i][j] = k*point[i-1] + dp[i-1][j-k*time[i-1]])， 即 dp[i][j] = max(k*point[i-1] + dp[i-1][j-k*time[i-1]]|0<=k<=j/time[i-1])。

最终 dp[N][M] 即为最多分数。
从 dp 最后一行依次往第一行即从最后一种题型开始往第0种题型求每种题型选择的题目数。
设当前行为 i，列为 j，最多分数为 p，则求出 k（0<=k<=j/time[i-1]），使得 p == k*point[i-1] + dp[i-1][j-k*time[i-1]]，则 k 为第 i-1 种题型选择的题目数。令 j -= k*time[i-1]，p -= k*point[i-1]，后求 dp[i-1] 行即第 i-2 种题型选择的题目数。

具体代码见附件。