0-1背包有关问题（动态规划）

0-1背包问题（动态规划）

<span style="font-size:18px;">#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
#include<string>
using namespace std;

/*
*0-1背包问题（动态规划）
*/

vector<vector<int>> values;//values[i][j]表示在前i个物品中能够装入容量为j的背包中的物品的最大值   (二维数组方案二)

void knapsack(vector<int>& w,vector<int>& v,int n,int vol)
{
	//有列到行的去遍历二维数组values并且填表
	for (int i = 0; i <= vol; i++)//列
	{
		for (int j = 0; j <= n ; j++)//行
		{
			if(i==0||j==0)
				values[j][i] = 0;
			else
			{
				if(i<w[j])
				{
					values[j][i] = values[j-1][i];
				}else
				{
					values[j][i] = max(values[j-1][i],values[j-1][i-w[j]]+v[j]);
				}
			}
		}
	}
}

void PrintRes(vector<int>& w,int i,int vol)
{
	if(i<=0)
		return ;
	if(values[i][vol]>values[i-1][vol])
	{
	  PrintRes(w,i-1,vol-w[i]);
	  cout<<i<<"   ";
	}
	else
	{
		PrintRes(w,i-1,vol);
	}
}
int main()
{
	vector<int> w;//物品的重量
	vector<int> v;//物品的价值
	int vol;
	w.push_back(0);//
	v.push_back(0);//
	copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(w));
	cin.clear();
	cin.sync();
	copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(v));
	cin.clear();
	cin.sync();
	cin>>vol;

	//创建和初始化v数组
	values = vector<vector<int>>(w.size(),vector<int>(vol+1,0));
	//运行查找解决方案的函数
	knapsack(w,v,w.size()-1,vol);
	//输出0-1背包结果
	cout<<"(动态规划：)被装进包内的物品为第 ";
	PrintRes(w,w.size()-1,vol);
	cout<<"个！"<<endl;
}</span>

   输入示例：

   第一行输入各个物品的重量

   第二行输入各个物品的价值

   第三行输入背包的最大承受重量