最优化原理和无后效性
假设完全背包的解为F(n1,n2,...,nN)（n1，n2 分别代表第1、第2件物品的选取数量），
完全背包的子问题为，将前i种物品放入容量为t的背包并取得最大价值，其对应的解为：F(n1,n2,...,ni)，
假设该解不是子问题的最优解，即存在另一组解F(m1,m2,...,mi)，使得F(m1,m2,...,mi) > F(n1,n2,...,ni)，
那么F(m1,m2,...,mi,...,nN) 必然大于 F(n1,n2,...,nN)，因此 F(n1,n2,...,nN) 不是原问题的最优解，
与原假设不符，所以F(n1,n2,...,ni)必然是子问题的最优解。

对于子问题的任意解，都不会影响后续子问题的解，也就是说，前i种物品如何选择，
只要最终的剩余背包空间不变，就不会影响后面物品的选择。即满足无后效性。

 #include <iostream>
 #include <algorithm>
 using namespace std;
 int N, V;
 int w[1111], v[1111], dp[1111][1111];
 int main()
 {
     cin >> N >> V; //物品容量&总容量
     for (int i = 1; i <= N; i++)
         cin >> v[i] >> w[i];
     for (int i = 1; i <= N; i++)
     {
         for (int j = 1; j <= V; j++)
         {
             for (int k = 0; k * v[i] <= j; k++)                               // 依次遍历装k个i的情况
                 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]); // 把01转换成0n
             // cout << dp[i][j] << " ";
         }
         // cout << endl;
     }
     cout << dp[N][V];
     system("pause");
 }



----------



 #include <iostream>
 #include <algorithm>
 using namespace std;
 int N, V;
 int w[1111], v[1111], dp[1111][1111];
 int main()
 {
     cin >> N >> V; //物品容量&总容量
     for (int i = 1; i <= N; i++)
         cin >> v[i] >> w[i];
     for (int i = 1; i <= N; i++) // 从1号物体开始计算，逐渐增加可选物品
     {
         for (int j = 1; j <= V; j++) // 从临时容量1开始计算，逐渐增加至最大容量；临时容量为0无意义，任意物体体积都不为0，无法装入
         {
             if (j < v[i])
                 dp[i][j] = dp[i - 1][j];
             else
                 dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]); // 此处和01背包的不同之处为使用dp[i][j - v[i]] + w[i]更新，即之前的背包可以装有i号物品
             // cout << dp[i][j] << " ";
         }
         // cout << endl;
     }
     cout << dp[N][V];
     system("pause");
 }


----------


 一维数组优化
#include <iostream>
#include <algorithm>
using namespace std;
int N, V;
int w[1111], v[1111], dp[1111];
int main()
{
    cin >> N >> V; // 物品容量&总容量
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];     // 体积&价值
    for (int i = 1; i <= N; i++) // 从1号物体开始计算，逐渐增加可选物品
    {
        for (int j = v[i]; j <= V; j++) // j=v[i] => 临时容量小于物体体积无意义，从前开始遍历可以用新更新的数据，代表使用多个i物品
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);  // i号物品的价值加上剩余的背包空间的最大价值
            // cout << dp[i] << " ";
        }
        // cout << endl;
    }
    cout << dp[V];
    system("pause");
}