c++实现动态规划算法解决0-1背包问题
Main.cpp
//============================================================================
// Name : Knapsack.cpp
// Author :
// Version : 1.0
// Copyright : Your copyright notice
// Description : 0-1背包算法问题
//============================================================================
#include <iostream>
#include<cstdlib>
#include"Knapsack.h"
#include<fstream>
#include <string>
using namespace std;
const char up='|';
const char left='-';
const char least='\\';
int** result; //结果列表
int *weight; //物品重量数组
int *value; //价值数组
void fileInit(int &n,int &max)//
{
ifstream in("input.txt"); //read file
if(!in){cout<<"file is not exist!";return;}
int num;
int maxWeight;
in>>num;
in>>maxWeight;
cout<<endl<<"物品数量："<<num<<endl<<"最大重量："<<maxWeight<<endl;
weight=new int[num];
value=new int[num];
cout<<"重量数组：\t";
for(int i=0;i<num;i++){in>>weight[i];cout<<setw(5)<<weight[i];}
cout<<endl;
cout<<"价值数组：\t";
for(int i=0;i<num;i++){in>>value[i];cout<<setw(5)<<value[i];}
cout<<endl;
n=num;
max=maxWeight;
in.close();
}
int main() {
cout << "0-1背包问题演示" << endl<<"从文件input.txt中初始化数据"; // prints Title
int number=0; //物品数量
int maxWeight=0; //背包最大重量
fileInit(number,maxWeight);
if(number==0){return 0;}
result=new int *[number+1];
for(int i = 0;i <= number;i++)
{
result[i]=new int[maxWeight+1];
}
//int* location; //最优解集合
inItResult(result,number+1,maxWeight+1); //init the result
cout<<"the init table is:"<<endl;
print(result,number+1,maxWeight+1);
cout<<"the result table is:"<<endl;
myKnapsack(value,weight,maxWeight,number,result);
print(result,number+1,maxWeight+1); //打印结果表格
cout<<endl<<"最大值为："<<result[number][maxWeight]<<endl;
system("pause");
return 0;
}
#include<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
//打印结果矩阵
template<class Type>
void print(Type** m,int n,int c)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<c;j++)
{
cout<<setw(5)<<m[i][j];
}
cout<<endl;
}
}
//初始化结果矩阵
template<class Type>
void inItResult(Type** result,int n,int c)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<c;j++)
{
result[i][j]=0;
}
}
}
//动态规划算法
template<class Type>
void myKnapsack(Type *v,int* w,int c,int n,Type** m)
{
for(int i=1;i<n+1;i++){
for(int j=1;j<c+1;j++)
{
if(w[i-1]<=j){
if(v[i-1]+m[i-1][j-w[i-1]]<m[i-1][j])
m[i][j]=m[i-1][j];
else m[i][j]=v[i-1]+m[i-1][j-w[i-1]];
}else{
m[i][j]=m[i-1][j];
}
}
}
}
转播
