C++动态规划之背包问题解决方法
本文实例讲述了C++动态规划之背包问题解决方法。分享给大家供大家参考。具体分析如下：
问题描述：
背包的最大容量为W,有N件物品，每件物品重量为w,价值为p，怎样选择物品能使得背包里的物品价值最大？
输入：
103 (W,N)
45 (w,p)
67 (w,p)
89 (w,p)
实现代码：
#include<stdio.h>
#defineTHING20
#defineWEIGHT100
intarr[THING][WEIGHT];
/*背包容量为weight，依次尝试1-thing物品时的最大价值*/
intprice[100];/*物品价格表*/
intweight[100];/*物品重量表*/
intmain()
{
inti,j;
intmax_weight,max_thing;
/*初始化*/
for(i=0;i<THING;++i)
{
for(j=0;j<WEIGHT;++j)
arr[i][j]=0;
}
/*读入数据*/
scanf("%d%d",&max_weight,&max_thing);
for(i=1;i<=max_thing;++i)
{
scanf("%d%d",&weight[i],&price[i]);
}
/*计算*/
for(i=1;i<=max_thing;++i)
{
for(j=1;j<=max_weight;++j)
{
if(j>=weight[i])
/*如果当前物品的容量小于背包容量
（当前物品能放进去）*/
{
/*如果当前物品的价值+背包剩余空间能放进去的物品价值
(之间计算过的最佳方案)*/
/*大于上一次选择的价值，则放入当前物品*/
if(price[i]+arr[i-1][j-weight[i]]>arr[i-1][j])
arr[i][j]=price[i]+arr[i-1][j-weight[i]];
else/*否则继续沿用上次的选择*/
arr[i][j]=arr[i-1][j];
}
else/*当前物品放不进去，继续沿用上次的选择*/
arr[i][j]=arr[i-1][j];
}
}
/*输出最优解*/
printf("maxweight:%d\n",arr[max_thing][max_weight]);
/*输出所有子解arr[][]*/
for(i=0;i<=max_thing;++i)
{
for(j=0;j<=max_weight;++j)
printf("%3d",arr[i][j]);
printf("\n");
}
return0;
}
希望本文所述对大家的C++程序设计有所帮助。