背包问题解法

网站建设770 更新时间：2025-06-08 23:45:15

2023年8月1日发(作者：)

使用穷举法解决0—1背包问题

问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中，限制重量为tw.考虑一个n元组（x0，x1，…，xn-1），其中xi=0 表示第i个物品没有选取，而xi=1则表示第i个物品被选取。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n元组，就可以得到问题的解。

显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0～2n-1.因此，如果把0～2n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。

下面是我据此思路编的一个小程序。

#include

#define MAX 100 // 限定最多物品数

/*将n化为二进制形式，结果存放到数组b中*/

void conversion(int n,int b[MAX])

{

int i;

for(i=0;i

{

b[i] = n%2;

n = n/2;

if(n==0)break; }

}

void main()

{

int i,j,n,b[MAX],temp[MAX];

float tw,maxv,w[MAX],v[MAX],temp_w,temp_v;

printf("please input n:n");

scanf("%d",&n); // 输入物品个数

printf("please input tw:");

scanf("%f",&tw); // 输入背包的限制重量

/*输入各个物品的重量*/

for(i=0;i

{

printf("please input the weight of w[%d]:n",i);

scanf("%f",&w[i]);

}

/*输入各个物品的价值*/

for(i=0;i

{

printf("please input the value of v[%d]:n",i);

scanf("%f",&v[i]); }

maxv = 0;

/*穷举2n个可能的选择，找出物品的最佳选择*/

for (i=0;i

{

for (j=0;j

{

b[j] = 0;

}

conversion(i,b);

temp_v = 0;

temp_w = 0;

for (j=0;j

{

if (b[j]==1)

{

temp_w = temp_w+w[j];

temp_v = temp_v + v[j];

}

/*试探当前选择是否是最优选择，如果是就保存下来*/

if ((temp_w < tw)&&(temp_v>maxv))

{ for (j=0;j

{

temp[j] = 0;

}

maxv = temp_v;

for (j=0;j

{

temp[j] = b[j];

}

printf("the max values is %f:n",maxv); // 输出放入背包的物品的最大价值

printf("the selection is:n");

/*输出物品的选择方式*/

for (j=0;j

{

printf("%d ",temp[j]);

}

程序在VC6.0，win xp下编译运行成功。程序测试结果，截图如下：

背包问题的递归算法

#include

//物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了

#define N 100

int n ;

//物品总种数

double limitW ;

//限制的总重量

double totV ;

//全部物品的总价值

double maxv ;

//解的总价值

int option[N];

//解的选择

int cop[N];

//当前解的选择

struct

{

//物品结构

double weight ; double value ;

}a[N];

//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值

void find(int i,doubletw,double tv)

{

int k ;

//物品i包含在当前方案的可能性

if(tw+<=limitW)

{

cop=1 ;

if(i

{

find(i+1,tw+,tv);

}

else

{

for(k=0;k

option[k]=cop[k];

maxv=tv ;

}

cop=0 ;

//物品i不包含在当前方案的可能性

if(>maxv)

{ if(i

{

find(i+1,tw,);

}

else

{

for(k=0;k

option[k]=cop[k];

maxv= ;

}

void main()

{

int k ;

double w,v ;

printf("输入物品种数:");

scanf("%d",&n);

printf("输入各物品的重量和价值:");

for(totV=0.0,k=0;k

{

scanf("%lf%lf",&w,&v);

a[k].weight=w ;

a[k].value=v ;

totV+=v ; }

printf("输入限制重量:");

scanf("%lf",&limitW);

maxv=0.0 ;

for(k=0;k

cop[k]=0 ;

find(0,0.0,totV);

for(k=0;k

if(option[k])

printf("%4d",k+1);

printf("总价值为: %2f",maxv);

}

0/1背包问题的递归算法(2006-4-21 19:52:00)

/*#include

#define N 100 //物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了

int n;//物品总种数

double limitW;//限制的总重量

double totV;//全部物品的总价值

double maxv;//解的总价值

int option[N];//解的选择

int cop[N];//当前解的选择

struct {//物品结构

double weight;

double value;

}a[N];

//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值

void find(int i,double tw,double tv)

{

int k;

//物品i包含在当前方案的可能性

if(tw+a[i].weight <= limitW){

cop[i]=1;

if(i

for(k=0;k

option[k]=cop[k];

maxv=tv;

}

cop[i]=0;

//物品i不包含在当前方案的可能性

if(tv-a[i].value>maxv){

if(i

else{

for(k=0;k

option[k]=cop[k];

maxv=tv-a[i].value;

}

void main()

{

int k;

double w,v;

printf("输入物品种数:");

scanf("%d",&n);

printf("输入各物品的重量和价值:");

for(totV=0.0,k=0;k

scanf("%lf %lf",&w,&v);

a[k].weight = w;a[k].value = v;

totV += v;

}

printf("输入限制重量:");

scanf("%lf",&limitW);

maxv=0.0;

for(k=0;k

find(0,0.0,totV);

for(k=0;k

if(option[k])printf("%4d",k+1);

printf("总价值为: %2f",maxv);

}

0/1背包问题 c++实现动态规划算法

2008-11-23 23:28

#include

using namespace std;

const int C=10;

const int N=5;

template

T max(const T a,const T b)

{

return a>b?a:b;

}

/*01背包问题

m为记录数组 m[i][j]代表在有j容量的条件下，从i开始往后的物品中可以取得的最大价值

w为质量数组，v为价值数组

n为物品个数，c为开始容量

*/

void knapsack(int **m,const int n,const int c,const int *w,const int *v)

{

/*

m[n][j]首先计算

m[n][j]的意思是容量为j ，放第n个物品可以取得的最大价值，当然当j比此物品的重量小时，装不下，m[n][j]为0

当j比此物品重量小时，能取得的最大价值就是v[n]

*/

for(int i=0;i

m[n][i]=0;

for(i=w[n];i<=c;i++)

m[n][i]=v[n];

/*

计算完m[n][1，2，3……]后就可以用递推公式

*/

for(i=n-1;i>1;i--)

{

for(int j=0;j

m[i][j]=m[i+1][j];

for(j=w[i];j<=c;j++)

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

} m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);

}

void traceback(int **m,int n,int c,int *x,int *w)

{

for(int i=1;i

{

if(m[i][c]==m[i+1][c])x[i]=0;

else

{

x[i]=1;

c-=w[i];

}

x[n]=(m[n][c]==0)?0:1;

}

int main()

{

int *v=new int[N+1];

int *w=new int[N+1];

int **m=new int*[N+1];

int *x=new int [N+1];

for(int i=0;i

{

m[i]=new int[C+1];

}

cout<<"输入质量序列,"<

for(i=1;i<=N;i++)

cin>>w[i];

cout<<"输入价值序列,"<

for(i=1;i<=N;i++)

cin>>v[i];

knapsack(m,N,C,w,v);

traceback(m,N,C,x,w);

cout<

for(i=1;i<=N;i++) cout<

for(i=0;i

{

delete [C+1]m[i];

}

delete [N+1] m;

return 1;

}

背包算法

2009-04-16 21:07

/**

* 背包问题

* 背包问题是计算机科学里的经典问题。在最简单的形式中，包括试图将不同重量的数据项放到

* 背包中．以使背包最后达到指定的总重量。不需要把所有的选项都放入背包中。

* 举例来说，假设想要背包精确地承重20磅，并且有5个可以选择放入的数据项，它们的重量

* 依次为11磅、8磅、7磅、6磅和5磅。对于选择放入的数据项数量不大时，人类很善于通过观察

* 就可以解决这个问题。于是大概可以计算出只有8磅、7磅和5磅的数据项加在一起和为20磅。

* 如果想要计算机来解决这个问题，就需要给计算机更详细的指令。算法如下：

* 1．如果在这个过程中的任何时刻，选择的数据项的总和符合目标重量，工作就完成了。

* 2．从选择第一个数据项开始。剩余的数据项的加和必须符合背包的目标重量减去第一个数据

* 项的重量；这是一个新的目标重量。

* 3．逐个地试每种剩余数据顶组合的可能性。但是，注意并不需要去试所有的组合，因为只要

* 数据顶朗和大于目标重量的时候，就停止添加数据项。

* 4．如果设有组合合适的话，放弃第—‘个数据项，并且从第二个数据项开始再重复一边整个

* 过程。

* 5．继续从第三个数据项开始，如此下去直到你已经试过所有的组合，这时知道没有解决答案

* 。

* 在刚刚描述的这个例子中，从11开始。现在想要剩余的数据项和为9(20减去u)。对于9，

* 从很小的8开始。现在想要剩余的数据项和为1(9减去8)。从7开始，但是它大于L，于是尝

* 试6，然后试5*它们都太大了d现在已经试过了所有的数据项，所以知道包含8的任何组合

* 和都不可能为9。接着尝试7，于是现在开始找的目标为2(9减去7)。

*

*/

public class Beibao{

static int[] a=new int[5]; //背包重量

static int[] b=new int[5]; //结果数组

static int flag=0; //下一个候选项

static int bound=20; //总重量

static int totle=0; //每次选择后的总重量

public static void inserttry(int i,int leftbound,int t){

if(i<5&&leftbound<=totle){

if(a[i]

b[t++]=a[i];

totle=totle-a[i];

leftbound=leftbound-a[i];

i++;

inserttry(i,leftbound,t);

}

else if(a[i]>leftbound){

totle=totle-a[i];

i++;

inserttry(i,leftbound,t);

}

else {

b[t]=a[i];

return;

}

else {

leftbound=leftbound+b[--t];

for(int f=0;f<5;f++)

{

if (a[f]==b[t]) {flag=++f; break;}

}

b[t]=0;

totle=0;

for(int m=flag;m<5;m++)

{ totle+=a[m];

}

inserttry(flag,leftbound,t);

}

return;

}

public static void main(String[] args){

a[0]=11;

a[1]=8;

a[2]=6;

a[3]=7;

a[4]=5;

for(int i=0;i<5;i++) { b[i]=0;}

for(int i=0;i<5;i++) {

totle+=a[i];

}

inserttry(0,20,0);

for(int i=0;i<5;i++){

n(b[i]);

}

这还有一个动态规划的算法

动态规划/贪心算法----0/1背包问题AND普通背包问题

/simon_ghost/archive/2006/11/20/

看懂了这个算法，这个是动态规划的，时间复杂度0（n）。

/course/3_program/c++/cppjs/20071023/

问题描述:

设U = {u1,u2,u3,ui}(一共有amount数量的物品)是一组准备放入背包中的物品.设背包的容量为size.

定义每个物品都具有两个属性weight和value.

我们要解决的问题就是计算在所选取的物品总重量不超过背包容量size的前提下使所选的物品总价值最大.

程序的设计:

设V[i, j]用来表示从前i项{u1ui}中取出来的装入体积为j的背包的最大价值.i的范围是从0到amount,j是从0到size.这样的话要计算的值就是V[amount, size].V[0, j]对于所有的j的值都是0,因为这时候的包中没有物品.同时V[i, 0]的值也是0,因为没有物品可以放到size为0的背包里面.

所以有:

V[i, j] = 0 若i = 0 或 j = 0;

V[i, j] = V[i - 1, j] 若j < ;(当物品的重量大于背包承重时,就不把物品放在里面)

V[i, j] = max{V[i - 1, j], V[i - 1, j - ] + } 若i > 0并且j >= ;

现在就可用动态规划的方法运用上面的公式来填表求解了.

#include

#define W 1000

#define N 1000

typedef struct data

{

int vaule;

int weight;

}goods;

int returnmax(int a, int b)

{

return (a > b ? a : b);

}

int KNAPSACK(goods *P, int a, int s)

{

int V[N][W];

int i,j,mv;

for(i = 0; i < a; i++)

V[i][0] = 0; for(j = 0; j < s; j++)

V[0][j] = 0;

for(i = 1; i <= a; i++)

for(j = 1; j <= s; j++)

{

V[i][j] = V[i - 1][j];

if(P[i].weight <= j)

V[i][j] = returnmax(V[i][j],V[i - 1][j - P[i].weight] +

P[i].vaule);

}

mv = V[a][s];

return mv;

}

int main()

{

int mostvalue,amount,size,i;

goods A[N];

printf("Input how much the goods have: ");

scanf("%d",&amount);

printf("Input the size of the bag: ");

scanf("%d",&size);

printf("Input the data of the goods: ");

for(i = 0; i < amount; i++)

scanf("%d %d",&A[i].vaule,&A[i].weight);

mostvalue = KNAPSACK(A,amount,size);

printf("%d",mostvalue);

return 0;

}

还有一种纯粹用数组解决的方案，避免了结构体的效率底下，思路是一样的

代码如下：

#include

#define GOODNUM 5

using namespace std;

int main()

{

int

good[GOODNUM][2]={{4,6},{5,2},{6,3},{7,7},{8,5}};//good[i][0]:size||good[i][1]:value

int i,j,size,weight; int v[GOODNUM+1][1000];

cout<<"please input the bag's size"<

cin>>size;

for(i=0;i<=GOODNUM;i++)

v[i][0]=0;

for(i=0;i<=size;i++)

v[0][i]=0;

for(i=1;i<=GOODNUM;i++)

for(j=1;j<=size;j++){

v[i][j]=v[i-1][j];

if(good[i-1][0]<=j)

if((v[i-1][j-good[i-1][0]]+good[i-1][1])>v[i][j])

v[i][j]=v[i-1][j-good[i-1][0]]+good[i-1][1];

}

cout<

}

2023年8月1日发(作者：)

使用穷举法解决0—1背包问题

问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中，限制重量为tw.考虑一个n元组（x0，x1，…，xn-1），其中xi=0 表示第i个物品没有选取，而xi=1则表示第i个物品被选取。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n元组，就可以得到问题的解。

显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0～2n-1.因此，如果把0～2n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。

下面是我据此思路编的一个小程序。

#include

#define MAX 100 // 限定最多物品数

/*将n化为二进制形式，结果存放到数组b中*/

void conversion(int n,int b[MAX])

{

int i;

for(i=0;i

{

b[i] = n%2;

n = n/2;

if(n==0)break; }

}

void main()

{

int i,j,n,b[MAX],temp[MAX];

float tw,maxv,w[MAX],v[MAX],temp_w,temp_v;

printf("please input n:n");

scanf("%d",&n); // 输入物品个数

printf("please input tw:");

scanf("%f",&tw); // 输入背包的限制重量

/*输入各个物品的重量*/

for(i=0;i

{

printf("please input the weight of w[%d]:n",i);

scanf("%f",&w[i]);

}

/*输入各个物品的价值*/

for(i=0;i

{

printf("please input the value of v[%d]:n",i);

scanf("%f",&v[i]); }

maxv = 0;

/*穷举2n个可能的选择，找出物品的最佳选择*/

for (i=0;i

{

for (j=0;j

{

b[j] = 0;

}

conversion(i,b);

temp_v = 0;

temp_w = 0;

for (j=0;j

{

if (b[j]==1)

{

temp_w = temp_w+w[j];

temp_v = temp_v + v[j];

}

/*试探当前选择是否是最优选择，如果是就保存下来*/

if ((temp_w < tw)&&(temp_v>maxv))

{ for (j=0;j

{

temp[j] = 0;

}

maxv = temp_v;

for (j=0;j

{

temp[j] = b[j];

}

printf("the max values is %f:n",maxv); // 输出放入背包的物品的最大价值

printf("the selection is:n");

/*输出物品的选择方式*/

for (j=0;j

{

printf("%d ",temp[j]);

}

程序在VC6.0，win xp下编译运行成功。程序测试结果，截图如下：

背包问题的递归算法

#include

//物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了

#define N 100

int n ;

//物品总种数

double limitW ;

//限制的总重量

double totV ;

//全部物品的总价值

double maxv ;

//解的总价值

int option[N];

//解的选择

int cop[N];

//当前解的选择

struct

{

//物品结构

double weight ; double value ;

}a[N];

//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值

void find(int i,doubletw,double tv)

{

int k ;

//物品i包含在当前方案的可能性

if(tw+<=limitW)

{

cop=1 ;

if(i

{

find(i+1,tw+,tv);

}

else

{

for(k=0;k

option[k]=cop[k];

maxv=tv ;

}

cop=0 ;

//物品i不包含在当前方案的可能性

if(>maxv)

{ if(i

{

find(i+1,tw,);

}

else

{

for(k=0;k

option[k]=cop[k];

maxv= ;

}

void main()

{

int k ;

double w,v ;

printf("输入物品种数:");

scanf("%d",&n);

printf("输入各物品的重量和价值:");

for(totV=0.0,k=0;k

{

scanf("%lf%lf",&w,&v);

a[k].weight=w ;

a[k].value=v ;

totV+=v ; }

printf("输入限制重量:");

scanf("%lf",&limitW);

maxv=0.0 ;

for(k=0;k

cop[k]=0 ;

find(0,0.0,totV);

for(k=0;k

if(option[k])

printf("%4d",k+1);

printf("总价值为: %2f",maxv);

}

0/1背包问题的递归算法(2006-4-21 19:52:00)

/*#include

#define N 100 //物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了

int n;//物品总种数

double limitW;//限制的总重量

double totV;//全部物品的总价值

double maxv;//解的总价值

int option[N];//解的选择

int cop[N];//当前解的选择

struct {//物品结构

double weight;

double value;

}a[N];

//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值

void find(int i,double tw,double tv)

{

int k;

//物品i包含在当前方案的可能性

if(tw+a[i].weight <= limitW){

cop[i]=1;

if(i

for(k=0;k

option[k]=cop[k];

maxv=tv;

}

cop[i]=0;

//物品i不包含在当前方案的可能性

if(tv-a[i].value>maxv){

if(i

else{

for(k=0;k

option[k]=cop[k];

maxv=tv-a[i].value;

}

void main()

{

int k;

double w,v;

printf("输入物品种数:");

scanf("%d",&n);

printf("输入各物品的重量和价值:");

for(totV=0.0,k=0;k

scanf("%lf %lf",&w,&v);

a[k].weight = w;a[k].value = v;

totV += v;

}

printf("输入限制重量:");

scanf("%lf",&limitW);

maxv=0.0;

for(k=0;k

find(0,0.0,totV);

for(k=0;k

if(option[k])printf("%4d",k+1);

printf("总价值为: %2f",maxv);

}

0/1背包问题 c++实现动态规划算法

2008-11-23 23:28

#include

using namespace std;

const int C=10;

const int N=5;

template

T max(const T a,const T b)

{

return a>b?a:b;

}

/*01背包问题

m为记录数组 m[i][j]代表在有j容量的条件下，从i开始往后的物品中可以取得的最大价值

w为质量数组，v为价值数组

n为物品个数，c为开始容量

*/

void knapsack(int **m,const int n,const int c,const int *w,const int *v)

{

/*

m[n][j]首先计算

m[n][j]的意思是容量为j ，放第n个物品可以取得的最大价值，当然当j比此物品的重量小时，装不下，m[n][j]为0

当j比此物品重量小时，能取得的最大价值就是v[n]

*/

for(int i=0;i

m[n][i]=0;

for(i=w[n];i<=c;i++)

m[n][i]=v[n];

/*

计算完m[n][1，2，3……]后就可以用递推公式

*/

for(i=n-1;i>1;i--)

{

for(int j=0;j

m[i][j]=m[i+1][j];

for(j=w[i];j<=c;j++)

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

} m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);

}

void traceback(int **m,int n,int c,int *x,int *w)

{

for(int i=1;i

{

if(m[i][c]==m[i+1][c])x[i]=0;

else

{

x[i]=1;

c-=w[i];

}

x[n]=(m[n][c]==0)?0:1;

}

int main()

{

int *v=new int[N+1];

int *w=new int[N+1];

int **m=new int*[N+1];

int *x=new int [N+1];

for(int i=0;i

{

m[i]=new int[C+1];

}

cout<<"输入质量序列,"<

for(i=1;i<=N;i++)

cin>>w[i];

cout<<"输入价值序列,"<

for(i=1;i<=N;i++)

cin>>v[i];

knapsack(m,N,C,w,v);

traceback(m,N,C,x,w);

cout<

for(i=1;i<=N;i++) cout<

for(i=0;i

{

delete [C+1]m[i];

}

delete [N+1] m;

return 1;

}

背包算法

2009-04-16 21:07

/**

* 背包问题

* 背包问题是计算机科学里的经典问题。在最简单的形式中，包括试图将不同重量的数据项放到

* 背包中．以使背包最后达到指定的总重量。不需要把所有的选项都放入背包中。

* 举例来说，假设想要背包精确地承重20磅，并且有5个可以选择放入的数据项，它们的重量

* 依次为11磅、8磅、7磅、6磅和5磅。对于选择放入的数据项数量不大时，人类很善于通过观察

* 就可以解决这个问题。于是大概可以计算出只有8磅、7磅和5磅的数据项加在一起和为20磅。

* 如果想要计算机来解决这个问题，就需要给计算机更详细的指令。算法如下：

* 1．如果在这个过程中的任何时刻，选择的数据项的总和符合目标重量，工作就完成了。

* 2．从选择第一个数据项开始。剩余的数据项的加和必须符合背包的目标重量减去第一个数据

* 项的重量；这是一个新的目标重量。

* 3．逐个地试每种剩余数据顶组合的可能性。但是，注意并不需要去试所有的组合，因为只要

* 数据顶朗和大于目标重量的时候，就停止添加数据项。

* 4．如果设有组合合适的话，放弃第—‘个数据项，并且从第二个数据项开始再重复一边整个

* 过程。

* 5．继续从第三个数据项开始，如此下去直到你已经试过所有的组合，这时知道没有解决答案

* 。

* 在刚刚描述的这个例子中，从11开始。现在想要剩余的数据项和为9(20减去u)。对于9，

* 从很小的8开始。现在想要剩余的数据项和为1(9减去8)。从7开始，但是它大于L，于是尝

* 试6，然后试5*它们都太大了d现在已经试过了所有的数据项，所以知道包含8的任何组合

* 和都不可能为9。接着尝试7，于是现在开始找的目标为2(9减去7)。

*

*/

public class Beibao{

static int[] a=new int[5]; //背包重量

static int[] b=new int[5]; //结果数组

static int flag=0; //下一个候选项

static int bound=20; //总重量

static int totle=0; //每次选择后的总重量

public static void inserttry(int i,int leftbound,int t){

if(i<5&&leftbound<=totle){

if(a[i]

b[t++]=a[i];

totle=totle-a[i];

leftbound=leftbound-a[i];

i++;

inserttry(i,leftbound,t);

}

else if(a[i]>leftbound){

totle=totle-a[i];

i++;

inserttry(i,leftbound,t);

}

else {

b[t]=a[i];

return;

}

else {

leftbound=leftbound+b[--t];

for(int f=0;f<5;f++)

{

if (a[f]==b[t]) {flag=++f; break;}

}

b[t]=0;

totle=0;

for(int m=flag;m<5;m++)

{ totle+=a[m];

}

inserttry(flag,leftbound,t);

}

return;

}

public static void main(String[] args){

a[0]=11;

a[1]=8;

a[2]=6;

a[3]=7;

a[4]=5;

for(int i=0;i<5;i++) { b[i]=0;}

for(int i=0;i<5;i++) {

totle+=a[i];

}

inserttry(0,20,0);

for(int i=0;i<5;i++){

n(b[i]);

}

这还有一个动态规划的算法

动态规划/贪心算法----0/1背包问题AND普通背包问题

/simon_ghost/archive/2006/11/20/

看懂了这个算法，这个是动态规划的，时间复杂度0（n）。

/course/3_program/c++/cppjs/20071023/

问题描述:

设U = {u1,u2,u3,ui}(一共有amount数量的物品)是一组准备放入背包中的物品.设背包的容量为size.

定义每个物品都具有两个属性weight和value.

我们要解决的问题就是计算在所选取的物品总重量不超过背包容量size的前提下使所选的物品总价值最大.

程序的设计:

设V[i, j]用来表示从前i项{u1ui}中取出来的装入体积为j的背包的最大价值.i的范围是从0到amount,j是从0到size.这样的话要计算的值就是V[amount, size].V[0, j]对于所有的j的值都是0,因为这时候的包中没有物品.同时V[i, 0]的值也是0,因为没有物品可以放到size为0的背包里面.

所以有:

V[i, j] = 0 若i = 0 或 j = 0;

V[i, j] = V[i - 1, j] 若j < ;(当物品的重量大于背包承重时,就不把物品放在里面)

V[i, j] = max{V[i - 1, j], V[i - 1, j - ] + } 若i > 0并且j >= ;

现在就可用动态规划的方法运用上面的公式来填表求解了.

#include

#define W 1000

#define N 1000

typedef struct data

{

int vaule;

int weight;