（1）0-1背包
容量为10的背包，有5种物品，每种物品只有一个，其重量分别为5，4，3，2，1，其价值分别为1，2，3，4，5。设计算法，实现背包内物品价值最大。（输出14）
（2）完全背包
容量为10的背包，有5种物品，每种物品数量无限，其重量分别为5，4，3，2，1，其价值分别为1，2，3，4，5。 设计算法，实现背包内物品价值最大。（输出50）
（3）多重背包
容量为10的背包，有5种物品，物品数量分别为1，2，1，2，1，重量分别为5，4，3，2，1，其价值分别为1，2，3，4，5。 设计算法，实现背包内物品价值最大。（输出16）
代码：
include<iostream>
include<vector>
using namespace std;
/* 第一种方法 0-1背包
void one_zero_packages(int num,int cap,vector<int> &val,vector<int> &weight,vector<vector<int>> &res)
{
for(int i=1;i<=num;i++)
{
for(int j=1;j<=cap;j++)
{
if(weight[i]>j)
res[i][j]=res[i-1][j];
else
res[i][j]=res[i-1][j]>res[i-1][j-weight[i]]+val[i]?res[i-1][j]:res[i-1][j-weight[i]]+val[i];
}
}
}
int main()
{
int num,cap;
cout<<"please input the numbers and capcity:"<<endl;
cin>>num>>cap;
cout<<"**************"<<endl;
vector<int > val(1,0);
vector<int > weight(1,0);
cout<<"please input the "<<num<<" values"<<endl;
for(int k=0;k<num;k++)
{
int tmp;
cin>>tmp;
val.push_back(tmp);
}
cout<<"please input the "<<num<<" weights"<<endl;
for(int k=0;k<num;k++)
{
int tmp;
cin>>tmp;
weight.push_back(tmp);
}
vector<vector<int>> res(num+1,vector<int>(cap+1,0));
one_zero_packages(num,cap,val,weight, res);
cout<<"The result is : "<<res[num][cap]<<endl;
system("pause");
return 0;
}
*/
int main()
{
int n=5,cap=10;
//int w[6]={0,5,4,3,2,1};
//int val[6]={0,1,2,3,4,5};
//int dp1[11]={0}; //0-1
//int dp2[11]={0}; //完全
//int dp3[11]={0}; //多重背包
//int cot[6]={0,1,2,1,2,1};
vector<int> w(1,0);
vector<int> val(1,0);
vector<int> dp1(cap+1,0);
vector<int> dp2(cap+1,0);
vector<int> dp3(cap+1,0);
vector<int> cot(1,0);
cout<<"please input the weights:"<<endl;
for(int i=0;i<n;i++)
{
int tmp;
cin>>tmp;
w.push_back(tmp);
}
cout<<"please input the values:"<<endl;
for(int i=0;i<n;i++)
{
int tmp;
cin>>tmp;
val.push_back(tmp);
}
cout<<"please input the counts:"<<endl;
for(int i=0;i<n;i++)
{
int tmp;
cin>>tmp;
cot.push_back(tmp);
}
//0-1背包
for(int i=0;i<6;i++)
{
for(int j=cap;j>=w[i];j--)
dp1[j]=dp1[j]>dp1[j-w[i]]+val[i]?dp1[j]:dp1[j-w[i]]+val[i];
}
//完全背包
for(int i=0;i<6;i++)
{
for(int j=w[i];j<=cap;j++)
dp2[j]=dp2[j]>dp2[j-w[i]]+val[i]?dp2[j]:dp2[j-w[i]]+val[i];
}
//多重背包
for(int i=0;i<6;i++)
{
for(int k=1;k<=cot[i];k++)
{
for(int j=cap;j>=w[i];j--)
dp3[j]=dp3[j]>dp3[j-w[i]]+val[i]?dp3[j]:dp3[j-w[i]]+val[i];
}
}
cout<<"The best result of 0-1 packages is: "<<dp1[cap]<<endl;
cout<<"The best result of full packages is: "<<dp2[cap]<<endl;
cout<<"The best result of multi-packages is: "<<dp3[cap]<<endl;
system("pause");
return 0;
}
解析：
完全背包都和0-1背包一样，就是遍历j时候的初始化不一样。
这里的dp[j]还是表示前i件物品放入一个为j容量的背包获得的最大价值，每次更新必然保证是当前最优解。就像求最长递增子序列一样。都是把所有情况过一遍然后拿最大的结果。
不多讲直接推算几步就全懂了。
1）首先是当只有物品1号的时候,j初始化为1号物品的重量为5
dp[5]=max(dp[5],dp[5-5]+1]=1
dp[6]到dp[9]都是1，dp[10]=2
2)然后现在是有物品1号和2号,j初始化为2号物品重量4
dp[4]=max(dp[4],dp[4-4]+2)=2
dp[5]=max(dp[5],dp[5-4]+2)=2
dp[..8]=max(dp[8],dp[8-4]+2)=4
其实到这里也差不多了，下面都是一样的。
我们要决定是不是要放这个物品，就从这个物品的大小出发遍历背包容量，然后每次遍历都对比下假如现在腾出这个物品的空间并且放进去比原来的价值还大的话，就放进去。
区别------------01背包和完全背包
01背包遍历是反向的，这样更新就不会影响前面的。
而完全背包正向遍历，会改变前面的所以也就可出现多次存放的了。
