登 录
#include<iostream><br /> using namespace std;<br /> int c[10][100];/*行代表是覆盖的背包个数，而列代表背包容量*/<br /> int Knapsack(int n,int m)<br /> {<br /> int i,j;<br /> int w[10],v[10];/*分别代表各个物品的重量和价值*/<br /> for(i=1;i<=n;i++)<br /> scanf("%d%d",&w[i],&v[i]);/*输入每个物品的重量W和价值V*/<br /> for(i=0;i<10;i++)/*初始化数组C*/<br /> for(j=0;j<100;j++)<br /> c[i][j]=0;<br /> for(i=1;i<=n;i++)/*物品覆盖得越来越多*/<br /> for(j=1;j<=m;j++)/*背包的容量则逐一测试*/<br /> {<br /> if(w[i]<=j)/*如果物品的重量小于当前背包的容量*/<br /> {<br /> /*如果当前物品的价值+剩余容量所能装载的最大价值〉在没有选择当前物品时的最大价值则更新C[][]；*/<br /> if(c[i-1][j]<v[i]+c[i-1][j-w[i]])<br /> c[i][j]=v[i]+c[i-1][j-w[i]];<br /> else//否则不更新<br /> c[i][j]=c[i-1][j];<br /> }<br /> else/*如果物品的重量大于当前背包的容量，那么这个物品不使用，这表明C[][]不变，则C[][]使用前面得到的最优解*/<br /> c[i][j]=c[i-1][j];<br /> }<br /> return c[n][m];<br /> }<br /> int main()<br /> {<br /> int n,m;/*n为背包个数，m为背包容量*/<br /> printf("input m and n/n");<br /> scanf("%d%d",&m,&n);<br /> printf("%d",Knapsack(n,m));<br /> printf("/n");<br /> int i,j;<br /> for(i=0;i<=n;i++)<br /> {<br /> for(j=0;j<=m;j++)<br /> printf("%3d",c[i][j]);<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br /> /*<br /> 测试用例为：<br /> 10 5//10是背包容量，5是背包个数<br /> 2 6<br /> 2 3<br /> 6 5<br /> 5 4<br /> 4 6<br /> */
#include<iostream><br /> using namespace std;<br /> int c[10][100];/*行代表是覆盖的背包个数，而列代表背包容量*/<br /> int x[10];//存放最优解<br /> int Knapsack(int n,int m,int w[],int v[])<br /> {<br /> int i,j;<br /> for(i=0;i<10;i++)/*初始化数组C*/<br /> for(j=0;j<100;j++)<br /> c[i][j]=0;<br /> for(i=1;i<=n;i++)/*物品覆盖得越来越多*/<br /> for(j=1;j<=m;j++)/*背包的容量则逐一测试*/<br /> {<br /> if(w[i]<=j)/*如果物品的重量小于当前背包的容量*/<br /> {<br /> /*如果当前物品的价值+剩余容量所能装载的最大价值〉在没有选择当前物品时的最大价值则更新C[][]；*/<br /> if(c[i-1][j]<v[i]+c[i-1][j-w[i]])<br /> {<br /> c[i][j]=v[i]+c[i-1][j-w[i]];<br /> }<br /> else//否则不更新<br /> {<br /> c[i][j]=c[i-1][j];<br /> }<br /> }<br /> else/*如果物品的重量大于当前背包的容量，那么这个物品不使用，这表明C[][]不变，则C[][]使用前面得到的最优解*/<br /> {<br /> c[i][j]=c[i-1][j];<br /> }<br /> }<br /> return c[n][m];//矩阵的最后一个为最优解。<br /> }<br /> void Trackback(int c[][100],int w[],int m,int n)<br /> {<br /> int i;<br /> for(i=n;i>0;i--)<br /> {<br /> if(c[i][m]==c[i-1][m])//表示序号为i的物品没有被装入背包<br /> x[i]=0;<br /> else<br /> {<br /> x[i]=1;<br /> m-=w[i];<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int n,m;/*n为背包个数，m为背包容量*/<br /> int i,j;<br /> printf("input m and n/n");<br /> scanf("%d%d",&m,&n);<br /> int w[10],v[10];/*分别代表各个物品的重量和价值*/<br /> for(i=1;i<=n;i++)<br /> scanf("%d%d",&w[i],&v[i]);/*输入每个物品的重量W和价值V*/<br /> printf("%d",Knapsack(n,m,w,v));<br /> printf("/n");<br /> for(i=0;i<=n;i++)<br /> {<br /> for(j=0;j<=m;j++)<br /> printf("%3d",c[i][j]);<br /> printf("/n");<br /> }<br /> Trackback(c,w,m,n);//找最优解<br /> for(i=1;i<=n;i++)<br /> cout<<x[i]<<" ";<br /> cout<<endl;<br /> return 0;<br /> }<br /> /*<br /> 测试用例为：<br /> //10是背包容量，5是背包个数<br /> 10 5<br /> 2 6<br /> 2 3<br /> 6 5<br /> 5 4<br /> 4 6<br /> */
抱歉!评论已关闭.