动态规划-完全背包（含全部代码）

题目：

假设你是一个小偷，有一个可放总重量为m(m<1000)的背包。现有n(n<32)件物品。
      总量分别为W1,W2,...，Wn。并且，物品具有价值，分别为V1,V2,...,Vn。m、n、Wi(1=<i<=n)均为正整数，
      并且，每种物品的数量不限，也就是说你可以重复拿一种物品。求能装入的最大总价值。
输入格式：
第一行为两个正整数m和n
接下来n行分别为n对整数，分别表示该物品的重量和价值。      
Example:
Input:
4 3
1 1500
3 2000
4 3000
Output：
6000

【分析】

1.状态表示
dp[i][j] 表示前i件物品放入容量为j的背包的最大价值。
2.状态转移方程：
dp[i][j] = dp[i-1][j],j<w[i]，即背包无法装下第i件物品
dp[i][j] = max(dp[i-1][j],dp[i][j-W[i]]+V[i])，j>=W[i]，即背包可以装下第i件物品。看装下后是否价值更高，后面举例讲解。
3.边界条件
dp[i][0]=0，dp[0][j] = 0

举个例子，对于第二件物品，背包小于他的重量3时，dp[2][j]=dp[1][j]，0<=j<=2，当j为3时，可以放入物品2，dp[1][3]为4500，dp[1][3-2]+V[i]=1500+2000=3500，也就是说从背包中拿出两个物品1，放入一个物品2并不会增大价值，所以还是4500。

代码：

/*
Project: dp_fullback
Date:    2019/01/11
Author:  Frank Yu
题目：假设你是一个小偷，有一个可放总重量为m(m<1000)的背包。现有n(n<32)件物品。
总量分别为W1,W2,...，Wn。并且，物品具有价值，分别为V1,V2,...,Vn。m、n、Wi(1=<i<=n)均为正整数，
并且，每种物品的数量不限，也就是说你可以重复拿一种物品。求能装入的最大总价值。
输入格式：
第一行为两个正整数m和n
接下来n行分别为n对整数，分别表示该物品的重量和价值。
Example:
Input:
4 3
1 1500
3 2000
4 3000
Output：
6000
【分析】
1.状态表示
dp[i][j] 表示前i件物品放入容量为j的背包的最大价值。
2.
状态转移方程：
dp[i][j] = dp[i-1][j],j<w[i]，即背包无法装下第i件物品
dp[i][j] = max(dp[i-1][j],dp[i][j-W[i]]+V[i])，j>=W[i]，即背包可以装下第i件物品。看装下后是否价值更高
3.边界条件
dp[i][j] = 0
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<iterator>
#include<algorithm>
#include<iostream>
#define maxm 1000
#define maxn 32
using namespace std;
int W[maxn], V[maxn];
//打印表 
void display(int dp[maxn][maxm], int n,int m)
{
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}
//主函数 
int main()
{
    int m, n;
    int dp[maxn][maxm];
    scanf("%d", &m);//背包重量 
    scanf("%d", &n);//物品种类 
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp[i][j] = 0;
    for (int i = 1; i <= n; i++)//下标即第几件物品,W[0]一直为0
    {
        scanf("%d", &W[i]);
        scanf("%d", &V[i]);
    }
    //填表 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (j < W[i])
            {
                dp[i][j] = dp[i - 1][j];
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - W[i]] + V[i]);
            }
    display(dp,n,m);
    cout << dp[n][m] << endl;
    return 0;
}

结果截图：

以下样例读者可自行画表，尝试手算和运行代码，结果可查看下一篇： 动态规划-完全背包优化

输入
6 3
2 3
4 7
3 6
输出
12