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 种题型选择的题目数。
具体代码见附件。