01背包定义

01背包问题是一个经典的问题，给定N个物品和一个背包。物品i的重量是Wi,其体积为Ci，背包的容量为C。问应该如何选择装入背包的物品，使得装入背包的物品的总重量为最大。

通常，背包类问题有以下三种考点

1、简单背包问题，即没有重量属性，只是判断能否刚好装满。
2、01背包，即要使能装下的前提下重量尽量大。
3、要求输出装入物品的方案或数量

// 01 背包模板  
#include <iostream>  
#include <string.h>  
using namespace std;  
  
int dp[21][1010];  
int w[21], c[21];  
  
int main() {  
    int N, V;  
    cin >> N >> V;//输入物品数量N  背包体积V  
    for (int i = 1; i <= N; ++i) {  
        cin >> w[i] >> c[i];//每个物品的重量wi 体积ci  
    }  
    //对于一个动态规划来说，最重要的是找到状态转移方程。   
    //在01背包问题中，一个物品要么装要么不装，那么我们可以得出下面的式子   
    //f[i,j]代表前i个物品背包容量最大为j最多能装的物品总重量   
    //f[i,j] = Max{ f[i-1,j-Ci]+Wi( j >= Ci ), f[i-1,j] }   
    //根据上面的状态转移方程可以写出下面的代码  
    for (int i = 1; i <= N; ++i) {  
        for (int j = 0; j <= V; ++j) {  
            if(j >= c[i]) {  
                dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);  
            }  
            else {  
                dp[i][j] = dp[i-1][j];  
            }  
        }  
    }  
    //dp[i][j]表示前i个物品装在j体积的背包中最大的重量  
    cout << dp[N][V] << endl;  
    return 0;  
}  

简单背包问题
题目描述：
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。
问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。
如果有满足条件的选择，则此背包有解，否则此背包问题无解。
输入描述：
输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）
多组测试数据。
输出描述：
对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO”
输入样例#...

练习题目

DreamJudge 1123 小偷的背包
DreamJudge 1567 Buyer
DreamJudge 1086 采药