动态规划-0/1背包问题（含全部代码）

题目：

假设你是一个小偷，有一个可放总重量为m(m<1000)的背包。现有n(n<32)件物品。
      总量分别为W1,W2,...，Wn。并且，物品具有价值，分别为V1,V2,...,Vn。m、n、Wi(1=<i<=n)均为正整数，
      现要求你尝试挑选几件物品,使这些物品重量之和为m。求能装入的最大总价值。
输入格式：
第一行为两个正整数m和n
接下来n行分别为n对整数，分别表示该物品的重量和价值。      
Example:
Input:
4 3
1 1500
3 2000
4 3000
Output：
3500  

【分析】

         假设物品1为吉他（G表示）、物品2为音响（S表示）、物品3为笔记本电脑（C表示）
          dp[i][j]表示前i件物品，在重量为j时的最大价值。很明显，出口即为第0行（没有物品）和第0列（没有背包空间）。

          状态转移方程
          dp[i-1][j]，W[i]>j（装不下，当没看见物品i吧）
          max（dp[i-1][j]，dp[i-1][j-W[i]]+V[i]） ，W[i]<=j（装的下，聪明的你选择装与不装的最佳方案）

手算模拟：

        假设你眼神不太好，仅看到吉他。我们先填前1件物品行，即吉他行。很明显，吉他占1磅，1、2、3、4列均是吉他，价值1500。

        这时，你又看到了音响，偷不偷呢？我们看前两件物品，前两列很明显，装不下音响（W[i]>j），没办法，偷不走。那么，是不是和没看见音响一样啊（dp[i][j]=dp[i-1][j]），即音响行1、2列复制吉他行。第三列可以装下音响（W[i]<=j），聪明的你经过比较发现音响价值更高【max（dp[i-1][j]，dp[i-1][j-W[i]]+V[i]）】，于是装了音响。那么，第四列呢？这就相当于你有两个背包，一个能放重量为3的，一个能放重量为1的（子问题加和），当前最优解为2000，那么多出来的能放重量为1的小背包的最优解是吉他。所以，重量为4时当然就加和在一起喽。

        最后，你发现了桌子上的笔记本电脑，那么装不装呢？装的话（价值3000），重量就减少了（dp[i-1][j-W[i]]+V[i]）。不装的话，价值（dp[i-1][j]，即3500）会比笔记本电脑多吗？答案是肯定的。所以，就当没看见笔记本电脑吧。

代码：

/*
Project:
Date:    2019/01/10
Author:  Frank Yu
题目：假设你是一个小偷，有一个可放总重量为m(m<1000)的背包。现有n(n<32)件物品。
      总量分别为W1,W2,...，Wn。并且，物品具有价值，分别为V1,V2,...,Vn。m、n、Wi(1=<i<=n)均为正整数，
      现要求你尝试挑选几件物品,使这些物品重量之和为m。求能装入的最大总价值。 
输入格式：
第一行为两个正整数m和n
接下来n行分别为n对整数，分别表示该物品的重量和价值。   
Example:
Input:
4 3 
1 1500
3 2000
4 3000
Output： 
3500  
【分析】 假设物品1为吉他（G表示）、物品2为音响（S表示）、物品3为笔记本电脑（C表示）
          dp[i][j]表示前i件物品，在重量为j时的最大价值。很明显，出口即为第0行（没有物品）和第0列（没有背包空间）。 
        状态转移方程 
    dp[i-1][j]，W[i]>j（装不下，当没看见物品i吧） 
        max（dp[i-1][j]，dp[i-1][j-W[i]]+V[i]） ，W[i]<=j（装的下，聪明的你选择装与不装的最佳方案）

*/
#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 m,int n)
{
         for(int i=0;i<=n;i++)
     {
      for(int j=0;j<=m;j++)
        cout<<dp[i][j];
        cout<<endl;
     }
     cout<<endl;
}
//主函数 
int main()
{
    int m, n;
    int dp[maxn][maxm];
    scanf("%d", &m);
    scanf("%d", &n);
    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(W[i]>j) dp[i][j]=dp[i-1][j];//第i件物品太重,放弃    
          else
           {
            int choose = dp[i-1][j-W[i]]+V[i];//选了，价值增加 
            int nochoose = dp[i-1][j];
            dp[i][j] =max(choose,nochoose);
           }          
        }
     }
     //display(dp,m,n);     
     cout<<dp[n][m]; 
    return 0;
}

结果截图：

此程序可以优化：动态规划-0/1背包优化（含全部代码）

0/1背包考虑了物品的重量和价值，但是每种物品只有一件，显然不符合现实。作为一名有眼力的小偷，如果手表即轻又贵，当然不要拿又重又相对便宜的笔记本电脑喽。

那么，考虑物品数量时又会如何呢？作有志气的小偷，请往下看。

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