?? 背包算法.cpp
字號:
#include<stdio.h>
#define N 100
double limitW,totV=0,maxv=0;
int option[N],cop[N],n,k;
struct
{
double weight;
double value;
}a[N];
void find(int i,double tw,double tv)
{
if(tw+a[i].weight<=limitW)
{
cop[i]=1;
if(i<n-1)
find(i+1,tw+a[i].weight,tv);
else
{
for(k=0;k<n;k++)
option[k]=cop[k];
maxv=tv;
}
cop[i]=0;
}
if(tv-a[i].value>maxv)
if(i<n-1)
find(i+1,tw,tv-a[i].value);
else
{
for(k=0;k<n;k++)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
void main()
{
printf("輸入物品種數:");
scanf("%d",&n);
printf("\n輸入各物品的重量和價值:");
for(k=0; k<n; totV+=a[k].value,k++)
scanf("%lf%lf",&a[k].weight,&a[k].value);
printf("\n輸入限制重量:");
scanf("%lf",&limitW);
for(k=0;k<n;k++)
cop[k]=0;
find(0,0,totV);
for(k=0;k<n;k++)
if(option[k])
printf("%4d",k+1);
printf("\n總價值為:%.3f\n",maxv);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -