if (i<n) //进入第i+1件的条件，还没有选完n种物品
if (tw+w[i]<=limit_w ) //选择第i件物品 find(i+1,tw+w[i],tv+v[i]); //进入第i+1件if (i<n) find(i+1,tw,tv); //不选择第i种物品 if (maxv<tv) maxv=tv; //发现有更大的价值，保留}void main(){ find(0,0,0); //从第0种物品开始选择，已有的重量tw和价值tv均为0printf("maxv=%d\n",maxv); }
#include <stdio.h>
#define M 10int w[M]={5,3,2,1}, v[M]={4,4,3,1}, limit_w=7, n=4; int maxv=0, b[M]={0} ;void find(int i,int tw,int tv){
if (i==n) return; //已对所有物品作了判断
if (tw+w[i]<=limit_w ) //选择第i件物品 { tw=tw+w[i]; tv=tv+v[i]; b[i]=1; //选了第i件 if (maxv<tv) maxv=tv; find(i+1,tw,tv); //进入第i+1件 tw=tw-w[i]; tv=tv-v[i]; b[i]=0; //恢复 } find(i+1,tw,tv); //不选择第i件物品}void main( ){ find(0,0,0); //从第0件物品开始选择 printf("maxv=%d\n",maxv); }
hnldyhy(303882171) 16:59:08
// 0-1背包问题的递归回溯算法：#include <stdio.h>#define M 10int w[M]={5,3,2,1}, v[M]={4,4,3,1}, limit_w=7, n=4;int tw=0, maxv=0, tv=0, b[M]={0} ;void find(int i) { if (i==n) return; //已对所有物品作了判断if (tw+w[i]<=limit_w ) //选择第i件物品{ tw=tw+w[i]; tv=tv+v[i]; b[i]=1; //选了第i件if (maxv<tv) maxv=tv;find(i+1); //进入第i+1件tw=tw-w[i]; tv=tv-v[i]; b[i]=0; //恢复}find(i+1); //不选择第i件物品}int main( ){ find(0); //从第0件物品开始选择printf("maxv=%d\n",maxv); }
***************************************************************************************
//程序1:动态规划法#include <stdio.h>#define MAX 20int n,c,w[MAX],v[MAX],m[MAX][MAX]={0};void knapsack(){ int i,j;for (i=1; i<=n; i++)for (j=1; j<=c; j++){ m[i][j]=m[i-1][j];if ( j>=w[i-1] && m[i-1][j-w[i-1]]+v[i-1]> m[i][j] ) m[i][j]=m[i-1][j-w[i-1]]+v[i-1];}}
//显示所取的物品及其重量（其中一个解）
//对数组m的最后一列检查来求解void disp( ){ int i,j;i=n;while ( m[i][c]==m[i-1][c] ) i--;while (i>0){ j=i-1;while (m[i][c]-m[j][c]!=v[i-1] && j>0)j--;printf("%5d%5d\n",w[i-1],v[i-1]);i=j;}} int main( ){ int i,j;printf("输入物品种数:"); scanf("%d",&n);printf("输入每种物品的重量与价值:\n");for (i=0; i<n; i++)scanf("%d%d",&w[i],&v[i]);printf("输入背包的总重量:\n"); scanf("%d",&c); knapsack(); disp();printf("最大价值=%d\n",m[n][c]);for (i=0; i<=n; i++){ for (j=0; j<=c; j++)printf("%3d",m[i][j]);printf("\n"); }}