动态规划-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（装的下，聪明的你选择装与不装的最佳方案）
          
          以上是未优化的01背包分析，为方便读者，没有删除，省得翻之前的文章了。
          由为优化的0/1背包分析可知，dp[i][j]只与上一行有关，因此，可以只保留一行。另外，W[i]与V[i]也可只保留一个。
          减少空间复杂度。
          dp[j]表示背包重量为j时，在看见前i件物品时的最高价值。
          状态转移方程：
          dp[j],W>j
          max(dp[j-W]+V,dp[j]),W<=j比较价值

代码：

/*
Project: dp_01bag_better
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。求能装入的最大总价值。 
输入格式：
第一行为两个正整数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（装的下，聪明的你选择装与不装的最佳方案） 

          以上是未优化的01背包分析，为方便读者，没有删除，省得翻之前的文章了。
          由为优化的0/1背包分析可知，dp[i][j]只与上一行有关，因此，可以只保留一行。另外，W[i]与V[i]也可只保留一个。
          减少空间复杂度。 
          dp[j]表示背包重量为j时，在看见前i件物品时的最高价值。
          状态转移方程：
          dp[j],W>j
          max(dp[j-W]+V,dp[j]),W<=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;
//打印表 
void display(int dp[maxm],int m)
{
    for(int i=0;i<=m;i++)
       cout<<dp[i]<<" ";
       cout<<endl;
}
//主函数 
int main()
{
    int m, n;
    int dp[maxm];
    memset(dp,0,sizeof(dp));
    scanf("%d", &m);
    scanf("%d", &n);
     //填表 
     for(int i=1;i<=n;i++)
     {
        int W,V;
        scanf("%d",&W);
        scanf("%d",&V);     
        for(int j=m;j>=W;--j)//从后向前 
        {
            int choose = dp[j-W]+V;//选了，价值增加 
            if(choose>dp[j])dp[j]=choose;      
        }
     }
     display(dp,m);//调试用 
     printf("%d",dp[m]);        
    return 0;
}

结果截图：

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