动态规划-简单背包问题（含全部代码）

题目：

假设你是一个小偷，有一个可放总重量为m(m<1000)的背包。现有n(n<32)件物品。
      总量分别为W1,W2,...Wn。m、n、Wi(1=<i<=n)均为正整数，现要求你尝试挑选几件物品
      使这些物品重量之和为m。若可以，输出那true。否则，输出false。
输入格式：
第一行为两个正整数m和n
第二行为n个正整数，分别表示n件物品的重量。      
Example:
Input:
10 5
1 2 3 4 5
Output:
true

【分析】

        dp[i][j]表示前i个能否满足重量j，能则为1。不能则为0。
         递归出口就表现在数组的第1行和第0列。行下标表示第几个物件，列下标表示重量。
         状态转移方程：
          dp[i][j]=dp[i-1][j]，W[i]>j第i件物品太重,放弃    
          dp[i][j] =max(dp[i-1][j-W[i]]，dp[i-1][j]),能放下，二叉树思想（选或不选思想），选的话减重量

代码：

/*
Project: dp_simple_bag
Date:    2019/01/10
Author:  Frank Yu
题目：假设你是一个小偷，有一个可放总重量为m(m<1000)的背包。现有n(n<32)件物品。
      总量分别为W1,W2,...Wn。m、n、Wi(1=<i<=n)均为正整数，现要求你尝试挑选几件物品
      使这些物品重量之和为m。若可以，输出那true。否则，输出false。
输入格式：
第一行为两个正整数m和n
第二行为n个正整数，分别表示n件物品的重量。    
Example:
Input:
10 5
1 2 3 4 5
Output:
true 
【分析】 dp[i][j]表示前i个能否满足重量j，能则为1。不能则为0。
         递归出口就表现在数组的第1行和第0列。行下标表示第几个物件，列下标表示重量。
         状态转移方程： 
          dp[i][j]=dp[i-1][j]，W[i]>j第i件物品太重,放弃   
          dp[i][j] =max(dp[i-1][j-W[i]]，dp[i-1][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];
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];
    memset(dp,0,sizeof(dp));
    scanf("%d", &m);
    scanf("%d", &n);
    for (int i = 1;i <= n;i++)//下标即第几件物品,W[0]一直为0
    {
        scanf("%d", &W[i]);
    }
    //初始化出口
     for(int i=1;i<=n;i++) //对应递归的m==0 
     {
        dp[i][0]=1;
     }
     for(int j=1;j<=m;j++)  
     {
        if(j==W[1]) dp[1][j]=1;//第一个物品就满足重量j 
         else dp[1][j]=0; 
     }
     //display(dp,m,n);
     //填表 
     for(int i=2;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]];
            int nochoose = dp[i-1][j];
            dp[i][j] =max(choose,nochoose);
           }          
        }
     }
    display(dp,m,n);//调试用       
    if(dp[n][m])
       printf("true");
    else printf("false"); 
    return 0;
}

结果截图：

那么，问题来了，作为一个小偷，塞满了背包就行了吗？有没有点出息。难道像无名之辈里面似的，不考虑价值，偷一背包模型机呀。当然不，我们还要考虑价值，做有见识的小偷！

请看考虑物品价值的0/1背包问题：动态规划-0/1背包问题（含全部代码）