背包类问题
标签: 机试攻略 - 高分篇
学习人数: 18.5k


高清播放
赞赏支持

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 采药


登录后开始许愿

1 条上岸许愿
Suehoo
2021年3月8日 21:27

v次把v成本

赞(0)