搜索+回溯的解释，贪心的不会，请版主指教。
在题目的意思输入是这样的时候
10 ，9，7；
21；
这样就要进行回溯；
选择10，剩余11；
选择10，剩余1；不成立；
转回剩余11；选择9，剩余2，不成立；
转回剩余11；选择7，剩余4；不成立；
转回剩余21；选择9，剩余12；
选择9，剩余2；不成立；
转回剩余12；选择7，剩余5；不成立；
转回剩余21；选择7，剩余14；
转回剩余14；选择7，剩余7；
转回剩余14；选择7，剩余0；成立；
最后返回3；
不过好像会暴掉，数据太大了
----------------解决方案--------------------------------------------------------
这个就是贪心+回朔的啊.
你看,为什么要选10呢,因为10最大,最能满足使得钱的张数最少.这就是贪心.
如果币值不多的话,回朔做没有问题.
----------------解决方案--------------------------------------------------------
理解了，但是这道题的数据量很大，回溯很可能会暴掉，特别是在数据不满足条件的时候。
版主有没有什么更好的方法？
----------------解决方案--------------------------------------------------------
你的对于小数还可以 大了就不行了 超时
#include <iostream>
using namespace std;
int main()
{ int n,m,i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
int a[1000]={0},b[200000]={0};
for (i=0;i<n;i++)
scanf("%d",&a[i]);
for (i=0;i<n;i++)
b[a[i]]=1;
for (i=1;i<=m;i++)
for (j=0;j<n;j++)
{
if (i-a[j]>0)
if (b[i]==0)
{
if (b[i-a[j]]!=0)
b[i]=b[i-a[j]]+1;
}
else
{
if (b[i-a[j]]!=0&&b[i-a[j]]+1<b[i])
b[i]=b[i-a[j]]+1;
}
}
if (b[m]==0) printf("bad\n");
else printf("%d\n",b[m]);
}
return 0;
}
----------------解决方案--------------------------------------------------------
我的搜索+回溯 请教各位怎么改
#include <stdio.h>
#include <algorithm>
using namespace std ;
struct Coin
{
int value ;
int num ;
}T[11] ;
int comp(Coin a ,Coin b )
{
return a.value <= b.value ;
}
int main()
{
int i ;
int n ;
int m ,sum ;
while(scanf("%d%d",&n,&m ) != EOF)
{
for( i = 0 ; i < n ; i ++ )
{
scanf("%d",&T[i].value);
}
sort(T,T+n ,comp );
sum = 0 ;
int k = -1 ;
for( i = n-1 ; i >=0 ; i-- )
{
if( T[i].value <= m )
{
k = i ;
break;
}
}
while(k>0)
{
sum ++ ;
m = m - T[k].value ;
if(m<T[k-1].value )
m=m + T[k].value;
k=k-1;
printf("%d\n",m);
}
if(m == 0)
printf("%d\n",sum ) ;
else
printf("bad\n");
}
return 0 ;
}
----------------解决方案--------------------------------------------------------
昨天写的，应该过得了
这样回溯不会超界
[CODE]#include <iostream>
#include <algorithm>
using namespace std;
int cost[10001]={0};
int value[1000];
int testCost;
int n;
int find_money(int s,int j,int ang)
{
int a,b=0;
if(s==testCost)
return cost[ang]+1;
else if(s<testCost)
{ cost[s]=cost[ang]+1;
for(int i=j;i>0;i--)
{
a=s+value[i];
b=find_money(a,i,s);
if(b!=0)
return b;
}
}
else if(s>testCost)
return 0;
}
main()
{
int ans;
while(cin>>n>>testCost){
for(int i=1;i<=n;i++)
cin >>value[i];
sort(&value[1],&value[n+1]);
for(i=1;i<=n;i++)
cost[value[i]]=1;
for(i=n;i>0;i--)
{
ans=find_money(value[i],i,0);
if(ans!=0) {cout<<ans<<endl; break;}
}
if(i==0) cout<<"bad"<<endl;
memset(cost,0,10001);
}
return 0;
}[/CODE]
----------------解决方案--------------------------------------------------------
大哥 这组测试用例通不过
4 18
3 4 7 10
3
4 28
10 9 4 3
4
4 18
10 9 4 3
3
最后应该是
9 9 结果是2 而不是3
请指教
----------------解决方案--------------------------------------------------------
不好意思哈，回溯的时候有一些数据肯定过不了，还有一个做hash表的算法，你看下过得了不，但是要慢点。我同学写的，也不会超时；
[CODE]#include <iostream>
using namespace std;
int cost[10001],p;
void ad()
{
int i,k;
k=0;
while(cost[k]==0)
k++;
while(2*k<=p)
{
i=k;
while(i+k<=p)
{
if(cost[i+k])
cost[i+k]=(cost[i]+cost[k]<cost[i+k])?(cost[i]+cost[k]):cost[i+k];
else
cost[i+k]=cost[i]+cost[k];
i+=k;
}
for(i=k;i+k<=p;i++)
if(cost[i]&&cost[k]+cost[i]<cost[i+k])
cost[i+k]=cost[i]+cost[k];
i=k+1;
while(!cost[i])
i++;
k=i;
}
}
int main()
{
int n,t;
cin>>p;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>t;
cost[t]=1;
}
ad();
if(cost[p]==0)
cout<<"Impossible"<<endl;
else
cout<<cost[p]<<endl;
return 0;
}[/CODE]
----------------解决方案--------------------------------------------------------
没有写标准，第一个变量是cost，第二个是value的个数
----------------解决方案--------------------------------------------------------
还是不行
输入
13 4的时候
2 4 6 8
结果是2
----------------解决方案--------------------------------------------------------