کسی سورسی برای کوله پشتی داره؟ لطفا اگه کتاب یا سایتی در این مورد هست معرفی کنید:20:
Printable View
کسی سورسی برای کوله پشتی داره؟ لطفا اگه کتاب یا سایتی در این مورد هست معرفی کنید:20:
من این رو دارم نمی دونم به درد میخوره یا نه
کد:Algorithm greedy_knapsock(p,w,m,x,n)
//object ordered so that (P[i]/W[i])>(P[i+1]/W[i+1])
m=0
cu=m //remaning capacity
for i=1 to n
if w[i]>cu then exit
x[i]=1
cu=cu-w[i]
next i
if i<=n then x[i]=cu/w[i]
end
اين كد حل اون به روش 0 و 1 هست.
اما براي اين مسئله يك را حل بازگشتي بسيار خوب هم وجود دارد.کد:# include<iostream>
# include<cmath>
using namespace std;
void bi(int t[],int n){
for(int i=0; n!=0;i++){
t[i]=n%2;
n/=2;
}
}
int main()
{
int n,i,s,sum,b=-1;
cout<<"enter number of gold pocket :";
cin>>n;
cout<<"enter sum:";
cin>>s;
int temp[10]={0},a[10];
for( i=0;i<n;i++)
cin>>a[i];
for(int j=1;j<pow(2,n);j++){
bi(temp,j);
sum=0;
for(int k=0;k<n;k++){
if(temp[k]!=0)
sum+=a[k];}
if (sum==s){
for(int k=0;k<n;k++)
if (temp[k]==1)
cout<<a[k]<<" ";
b=1;
cout<<endl;}
}
if (b==-1)
cout<<"there is not such set"<<endl;
return 0;
}
Good Luck
دوستان ممنون از کمکتون:46:
این کد ها تا حدی کمکم کرد ولی با استفاده از الگوریتم greedy نوشته شده بود. برنامه به روش dynamic programming بیشتر به کار من میاد!
میتونین برام پیدا کنین؟:11:
اینم کد سی. الگوریتم knapsack به روش dynamic 0/1
این لینک ها رو هم ببین. مخصوصاً اولی رو چون قشنگ الگوریتمشو توضیح داده.کد:void Knapsack(){
int a[n, w], c[n], v[n], n, w, i, c;
for(c = 0; c <= w; c++){
a[0, c] = 0;
}
for(i = 1, i <= n; i++){
a[i, 0] = 0;
for(c = 1; c <= w; c++){
if(c[i] <= c){
if(v[i] + a[i-1, c-c[i]] > a[i-1, c])
a[i, c] = v[i] + c[i-1, c-c[i]];
else
a[i, c] = a[i-1, c];
}
else
a[i, c] = a[i-1, c];
}
}
}
کد:http://en.wikipedia.org/wiki/Knapsack_problem
اینم چند تا الگوریتم دیگه که تو اینترنت پیدا کردم:کد:http://www.mpi-inf.mpg.de/~rybal/armc-live-termin/node5.html
کد:http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm
کد:http://www-cse.uta.edu/~holder/courses/cse2320/lectures/l15/node12.html
کد:http://www.animal.ahrgr.de/showAnimationDetails.php3?lang=en&anim=18
واقعا دستتون درد نکنه،خیلی کامل بود .
مرسی:46:
ببین واسه کد صفر و یک الگوریتم کوله پشتی جایزه گذاشتن ، میدونستی؟
کد اون مدل دیگش رو نداری؟(اون که درصدی می تونیم برداریم)
salam mishe be ravesh bazgashti va harisane ro vase man mail konin
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
merciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
خیلی عالی بود مرسی:n16:نقل قول: