Question

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

输入有： 一个a[n]数组（都是正整数）。还有一个m（也是正整数）
现要从a数组中取出x个数（x<=n，且每个数只能取一次）
使得这x个数相加是最接近m的（小于或等于m）
求算法思路或代码。谢谢！
x个数相加是不能大于m的

Answer 1

二维费用背包问题。
我们把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 <stdio.h>
#include <string.h>
#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;
}

Answer 2

这个问题来自哪里啊，挺有意思的。
想到一个思路，不过不是用动态规划，我把她叫做《可行逐次逼近法》吧，想法如下：
1、数据结构
a[n]、pailie_a[n]、
2、思路
(1)获得初始次优可行解n
①将a[n]从小到大排列，排列后仍然存储在a[n]中，a[1]储存最小值，a[n]储存最大值；
②将重新排列后，各元素初始时的位置序号存在pailie_a[n]中，如最小的数，重排后储存在a[1]中，原始状态储存在a[k]中，则pailie_a[1]=k；
③判断有无可行解：
将a[n]的前x个最小值，取出来，存在solve[x]中，计算sum（solve[x]），if超过给定的，无可行解；
否则，有可行解，并且此时的solve[x]即为初始次优可行解，将a[n]中剩余元素存在qita[n-x]中备用；
（2）逐次逼近最优解：
依次：用qita[n-x]中的一个元素替换掉solve[x]中的一个元素；
直至：满足停止准则：用qita[n-x]中的任何一个元素替换掉solve[x]中的任何一个元素都不会使结果更优。
………未完待续………

追问

pailie_a[n] 的用处是什么？ 期待你的答案。

追答

见上：②将重新排列后，各元素初始时的位置序号存在pailie_a[n]中，如最小的数，重排后储存在a[1]中，原始状态储存在a[k]中，则pailie_a[1]=k；

Answer 3

01背包问题，具体百度“背包九讲”，acm大神写的。

追问

....有没代码？