- 科技
- 求解01背包问题及左剪枝 回溯法
求解0/1背包问题及左剪枝
#include<stdio.h>
#define MAXN 20
int n
,W
,k
;
int w
[MAXN
],v
[MAXN
];
int x
[MAXN
];
int maxv
=0;
void dfs(int i
,int tw
,int tv
,int op
[])
{
if(i
>n
)
{
if(tw
==W
&&tv
>maxv
)
{
maxv
=tv
;
int j
;
for(j
=1;j
<=n
;j
++)
x
[j
]=op
[j
];
}
}
else
{
if(tw
+w
[i
]<=W
)
{
op
[i
]=1;
dfs(i
+1,tw
+w
[i
],tv
+v
[i
],op
);
}
op
[i
]=0;
dfs(i
+1,tw
,tv
,op
);
}
}
int main()
{
int op
[MAXN
];
scanf("%d",&n
);
scanf("%d",&W
);
for(k
=1;k
<=n
;k
++)
{
scanf("%d",&w
[k
]);
}
for(k
=1;k
<=n
;k
++)
{
scanf("%d",&v
[k
]);
}
dfs(1,0,0,op
);
printf("%d",maxv
);
return 0;
}
求解0/1背包问题 回溯法
求解0/1背包问题及左右剪枝 回溯法
Processed:
0.013, SQL:
8
