问题： 有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值
1≤n≤100
1≤wi，vi≤100
1≤W≤10000
思考： 其实这个问题01背包问题的区别在与，这里的每个物品都是可以重复取的。而01背包问题就只能取一次；
【dynamic|完全背包问题】在原01背包问题中:
递推式为： dp [ i ] [ j ] = max( dp[ i-1 ] [ j - weight [ i ] ] + value [ i ] , dp[ i-1 ] [ j ] )
式子的含义为 ： 当我背包的容量为 J 时，我是否取第 i 个物品
（1）如果取： **dp[i-1 ] [ j - weight [ i ] ] + value [ i ]** ：
背包要放入物品 **i** ， 那么背包必须有容纳得下 **i** 物品的空间 ，
所以前一状态背包用量有 ：**[ j - weight [ i ]]** ，
既然我的物品只能取一次，所以**[ i - 1 ]** (过度回取第 i- 1 号物品 的情况，保证i 号物品 只被取一次)， 才有此式子。
(2) 如果不取，那么就是直接返回前状态 ： dp[ i-1 ] [ j ]
那么ok， 我们现在想一想，如果我可以反复取 i 号物品（在容量J 允许的情况下） ，
那么如果我取了 i 号物品 一次后， 我就不需要过度回 取 i- 1 号物品的 状态了 。
因为假设取了一次之后，背包容量还可以再一次纳入此物品，那么 只需要在我取了第一次的基础上，在加一次就ok 啦。而第一次取得记录已经被记录入 dp [ i ] [ j - weight [ i ] ] + value[ i ] （为什么不是 i-1 ？？？ -----已经说了：可以多次取，不需要过度回 i-1 的状态来保证只取一次）了。
所以 最 终 结 论 完全背包问题 的 递 推 式 ：
dp[ i ] [ j - weight [ i ] ] + value [ i ] , dp[ i-1 ] [ j ]
举例：
| 物品 | 价值 | 重量 |
|---|---|---|
| 物品1 | 4 | 3 |
| 物品2 | 5 | 4 |
| 物品3 | 3 | 2 |
(直接跳到允许放入的时候)
1） dp [ 1 ] [ 3 ] = max( dp[ i ] [ 3-3 ] + value [ 1 ] , dp [ 0 ] [ 3 ] )
==> dp [1] [3] = max ( 0 + 4 , 0)
2）dp [ 1 ] [ 4 ] = max( dp[ 1 ] [ 4-3 ] + value [ 1 ] , dp [ 0 ] [ 4 ] )
==> dp [1]\ [4] = max ( 0 + 4 , 0)
3）dp [ 1 ] [ 5 ] = max( dp[ 1 ] [ 5-3 ] + value [ 1 ] , dp [ 0 ] [ 5 ] )
==> dp [1] [5] = max ( 0 + 4 , 0)
!!!重点来了
4）dp [ 1 ] [ 6 ] = max( dp[ 1 ] [ 6-3 ] + value [ 1 ] , dp [ 0 ] [ 6 ] )
dp [ 1 ] [ 6 ] = max( dp[ 1 ] [ 3 ] + value [ 1 ] , dp [ 0 ] [ 6 ] )
==> dp [1] [6] = max ( 4 + 4 , 0)
！！是不是在原来已经放了物品1的基础上又放了物品！！
如果是01背包问题就是:
dp [ 1 ] [ 6 ] = max( dp[ 1-1 ] [ 6-3]+ value [ 1 ], dp [ 0 ] [ 6 ] )
dp [ 1 ] [ 6 ] = max( dp[ 0 ] [ 3 ]+ value [ 1 ], dp [ 0 ] [ 6 ] )
==>dp [1] [6]= max（0 + 4,0)
代码
">#include
using namespace std;
int main()
{
int n;
int vol ;
cin>>n;
int value[n]={0};
int weight[n]={0};
int dp[10][10] ={0};
for(int i=1;
i<=n;
i++)
{
cin>>value[i];
}
for(int j=1;
j<=n;
j++)
{
cin>>weight[j];
}
cin>>vol;
for(int i=1;
i<=n;
i++)
{
for(int j=1;
j<=vol;
j++)
{
if(weight[i]<=j)
{
dp[i][j] = max(dp[i][j - weight[i]] + value[i], dp[i-1][j]);
}
else
{
dp[i][j] = dp[i-1][j];
}}
}
for(int i=1;
i<=n;
i++)
{
for(int j=1;
j<=vol;
j++)
{
cout<友情提示： 关于01背包问题，推荐一位博主：
[简书] 01背包问题
~第一次写博，可能很罗嗦，也可能有错误，欢迎指点，谢谢亲故 ~
推荐阅读
- Dynamic|Best Time to Buy and Sell Stock IV
- R|不同方法的正态性检验及R语言实现
- 拜占庭问题
- C|VS Code搭建C/C++编译运行环境
- PHP|2-1.（OOP）PHP异常处理