</pre><pre name="code" class="cpp">/*
=========程序信息========
对应题目：01背包之金矿模型
使用语言：c++
使用编译器：Visual Studio 2005.NET
使用算法：动态规划
算法运行时间：O(people * n) [people是人数，n是金矿数]
作者：贵州大学05级 刘永辉
昵称：SDJL
编写时间：2008年8月
联系QQ：44561907
E-Mail：44561907@qq.com
获得更多文章请访问我的博客：www.cnblogs.com/sdjl
如果发现BUG或有写得不好的地方请发邮件告诉我:)
转载请保留此部分信息:)
*/
/*
思考动态规划的第一点----最优子结构：
思考动态规划的第二点----子问题重叠：
思考动态规划的第三点----边界：
思考动态规划的第四点----子问题独立：
思考动态规划的第五点----做备忘录：
转移方程：
当mineNum = 0且people >= peopleNeeded[mineNum]时 f(people,mineNum) = gold[mineNum]
当mineNum = 0且people < peopleNeeded[mineNum]时 f(people,mineNum) = 0
当mineNum != 0时 f(people,mineNum) = f(people-peopleNeeded[mineNum], mineNum-1) + gold[mineNum]与f(people, mineNum-1)
中的较大者，前两个式子对应动态规划的“边界”，后一个式子对应动态规划的“最优子结构”请读者弄明白后再继续往下看。
*/
#include <iostream>
#include <fstream>
using namespace std;
const int max_n = 3;//程序支持的最多金矿数
const int max_people = 12;//程序支持的最多人数
int n;//金矿数
int peopleTotal;//可以用于挖金子的人数
int peopleNeed[max_n];//每座金矿需要的人数
int gold[max_n];//每座金矿能够挖出来的金子数
int maxGold[max_people][max_n];//maxGold[i][j]保存了i个人挖前j个金矿能够得到的最大金子数，等于-1时表示未知
//初始化数据
void init(){
ifstream inputFile("beibao10.in");
inputFile>>peopleTotal>>n;
for(int i=0; i<n; i++)
inputFile>>peopleNeed[i]>>gold[i];
inputFile.close();
for(i=0; i<=peopleTotal; i++)
for(int j=0; j<n; j++)
maxGold[i][j] = -1;//等于-1时表示未知 [对应动态规划中的“做备忘录”]
}
//获得在仅有people个人和前mineNum个金矿时能够得到的最大金子数，注意“前多少个”也是从0开始编号的
int GetMaxGold(int people, int mineNum){
//申明返回的最大金子数
int retMaxGold;
//如果这个问题曾经计算过 [对应动态规划中的“做备忘录”]
if(maxGold[people][mineNum] != -1){
//获得保存起来的值
retMaxGold = maxGold[people][mineNum];
}
else if(mineNum == 0){//如果仅有一个金矿时 [对应动态规划中的“边界”]
//当给出的人数足够开采这座金矿
if(people >= peopleNeed[mineNum]){
//得到的最大值就是这座金矿的金子数
retMaxGold = gold[mineNum];
}else{//否则这唯一的一座金矿也不能开采
//得到的最大值为0个金子
retMaxGold = 0;
}
}
else if(people >= peopleNeed[mineNum]){//如果给出的人够开采这座金矿 [对应动态规划中的“最优子结构”]
//考虑开采与不开采两种情况，取最大值.
int a=( GetMaxGold(people - peopleNeed[mineNum],mineNum -1) + gold[mineNum] );
int b= ( GetMaxGold(people,mineNum - 1) );
retMaxGold= a>b?a:b;
}
else{//否则给出的人不够开采这座金矿 [对应动态规划中的“最优子结构”]
//仅考虑不开采的情况
retMaxGold = GetMaxGold(people,mineNum - 1);
}
//做备忘录
maxGold[people][mineNum] = retMaxGold;
return retMaxGold;
}
int main(int argc, char* argv[]){
//初始化数据
init();
//输出给定peopleTotal个人和n个金矿能够获得的最大金子数，再次提醒编号从0开始，所以最后一个金矿编号为n-1
cout<<GetMaxGold(peopleTotal,n-1);
system("pause");
return 0;
}
下面是发现的另一段代码，效果也可以，较为简练
#include <iostream>
#include <vector>
using namespace std;
const int MIN=-65534;
const int N=3; //物品数量
const int V=5; //背包容量
int f[N+1][V+1];
int Package(int *W,int *C,int N,int V);
void main(int argc,char *argv[]){
int W[4]={0,7,5,8}; //物品权重
int C[4]={0,2,3,4}; //物品大小
int result=Package(W,C,N,V);
if(result>0){
cout<<endl;
cout<<"the opt value:"<<result<<endl;
int i=N,j=V;
while(i){
if(f[i][j]==(f[i-1][j-C[i]]+W[i])){
cout<<i<<":"<<"w="<<W[i]<<",c="<<C[i]<<endl;
j-=C[i];
}
i--;
}
}else
cout<<"can not find the opt value"<<endl;
return;
}
int Package(int *W,int *C,int N,int V){
int i,j;
memset(f,0,sizeof(f)); //初始化为0
for(i=0;i<=N;i++)
for(j=1;j<=V;j++) //此步骤是解决是否恰好满足背包容量，
f[i][j]=MIN; //若“恰好”满足背包容量，即正好装满背包，则加上此步骤，若不需要“恰好”，则初始化为0
for(i=1;i<=N;i++)
for(j=C[i];j<=V;j++){
f[i][j]=(f[i-1][j]>f[i-1][j-C[i]]+W[i])?f[i-1][j]:(f[i-1][j-C[i]]+W[i]);
cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl;
}
return f[N][V];
}