c++中new容易出现的问题
浏览数：15 /
时间：2015年06月08日
/* 01背包变型 一开始想的是n<=1000,价格最大为50 所以开了50005的数组
结果发现余额最大1000，所以数组不必开那么大
用5元取一个最大价值的，明显最优，所以先用5元减去一个最大值，就变成了01背包
所以最后输出的时候后 dp[cost-5]和减去一个max
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX(a,b) (a)>(b)?a:b
int dp[1005],a[1005];
int main()
{
int i,j,n,cost,max;
while(scanf("%d",&n),n)
{
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&cost);
sort(a,a+n);
max=a[n-1];
memset(dp,0,sizeof(dp));
if(cost<5) printf("%d\n",cost);
else
{
for(i=0; i<n-1; i++)
{
for(j=cost-5; j>=a[i]; j--)
{
dp[j]=MAX(dp[j],dp[j-a[i]]+a[i]);
}
}
printf("%d\n",cost-max-dp[cost-5]);
}
}
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
