精华内容
下载资源
问答
  • 背包问题求具体方案 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出 字典序...

    背包问题求具体方案

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

    第 i 件物品的体积是 vi,价值是 wi。

    求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

    输出 字典序最小的方案。这里的字典序是指:所选物品的编号所构成的序列。物品的编号范围是 1…N。

    输入格式
    第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

    接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

    输出格式
    输出一行,包含若干个用空格隔开的整数,表示最优解中所选物品的编号序列,且该编号序列的字典序最小。

    物品编号范围是 1…N。

    数据范围
    0<N,V≤1000
    0<vi,wi≤1000

    解题思路:

    首先要跑一遍01背包求出最优解,如果背包里放了这个物品的话,f[i][all]==f[i+1][all-v[i]]+w[i] ,从前往后遍历一遍即可。

    Code:

    #include<iostream>
    
    using namespace std;
    const int maxn=1e3+7;
    
    int f[maxn][maxn],v[maxn],w[maxn];
    
    int main(){
        int n,m;
        
        cin>>n>>m;
        
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        
        for(int i=n;i>=1;i--){                //因为要求字典序最小,倒着循环,如果能选编号小的就选编号小的
            for(int j=0;j<=m;j++){
                f[i][j]=f[i+1][j];
                if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
            }
        }
        
        int all=m;
        for(int i=1;i<=n;i++){
            if(f[i][all]==f[i+1][all-v[i]]+w[i]&&all>=v[i]){     //all要大于v[i]
                all-=v[i];
                cout<<i<<" ";
            }
        }
        puts("");
    }
    
    展开全文
  • 背包问题求方案数 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出 最优选法的...

    背包问题求方案数

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次

    第 i 件物品的体积是 vi,价值是 wi。

    求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

    输出 最优选法的方案数。注意答案可能很大,请输出答案模 1e9+7 的结果。

    输入格式
    第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

    接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

    输出格式
    输出一个整数,表示 方案数 模 109+7 的结果。

    数据范围
    0<N,V≤1000
    0<vi,wi≤1000

    解题思路:新建一个g[]数组,记录下背包装该体积的物品的方案数,并且求方案数,f[]数组要记得初始化为负无穷。

    Code:

    #include<iostream>
    #include<cstdio>
    
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+7;
    const int mod=1e9+7;
    
    ll f[maxn],g[maxn];
    ll v[maxn],w[maxn];
    
    int main(){
        
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=m;i++) f[i]=-0x3f3f3f3f;
        g[0]=1;
        
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        for(int i=1;i<=n;i++){
            for(int j=m;j>=v[i];j--){
                ll t=max(f[j],f[j-v[i]]+w[i]);
                ll s=0;
                if(t==f[j]) s+=g[j];
                if(t==f[j-v[i]]+w[i]) s+=g[j-v[i]];
                
                f[j]=t%mod;
                g[j]=s%mod;
            }
        }
        
        ll ans=0,maxx=0;
        for(int i=0;i<=m;i++) maxx=max(maxx,f[i]);
        
        for(int i=0;i<=m;i++){
            if(f[i]==maxx) ans+=g[i]; 
            ans%=mod;
        }
        
        cout<<ans<<endl;
        
    }
    
    展开全文
  • 题目:有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi,价值是 wi。...第一行两个整数,N,V,用空格隔开,分别表示物品数量背包容积。接下来有 N 行,每行两个整数 vi,w...

    题目:有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
    第 i 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出 字典序最小的方案。这里的字典序是指:所选物品的编号所构成的序列。物品的编号范围是 1…N。

    输入格式
    第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

    输出格式
    输出一行,包含若干个用空格隔开的整数,表示最优解中所选物品的编号序列,且该编号序列的字典序最小。物品编号范围是 1…N。

    数据范围
    0<N,V≤1000
    0<vi,wi≤1000

    解析:本题区别于背包九讲之八—背包问题求方案数,需要求得最佳答案后,反向寻找方案。由于字典序输出,运用贪心思想,编号小的物品能拿一定要拿。为此在记录 f 数组时从大号物品开始枚举,方便最后逆向寻找方案。

    Code:

    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N = 1010;
    int f[N][N], v[N], w[N];
    int main()
    {
        int n,V;
        cin>>n>>V;
        for(int i=1;i<=n;i++)    cin>>v[i]>>w[i];
        for(int i=n;i>=1;i--)
        {
            for(int j=0;j<=V;j++)
            {
                f[i][j] = f[i+1][j];
                if(j >= v[i])      f[i][j] = max(f[i][j],f[i+1][j-v[i]]+w[i]);
            }
        }
        int vol = V;
        for(int i=1;i<=n;i++)
        {
            if(vol >= v[i] && f[i][vol] == f[i+1][vol-v[i]]+w[i]) 
            {
                cout<<i<<" ";
                vol -= v[i];
            }
        }
        return 0;
    }
    

    ps:博主能力有限,如果读者发现什么问题,欢迎私信或评论指出不足。欢迎读者询问问题,乐意尽我所能解答读者的问题。欢迎评论,欢迎交流。谢谢大家!

    展开全文
  • 题目:有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。...第一行两个整数,N,V,用空格隔开,分别表示物品数量背包容积。接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表...

    题目:有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出 最优选法的方案数。注意答案可能很大,请输出答案模 1e9+7 的结果。

    输入格式
    第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

    输出格式
    输出一个整数,表示 方案数 模 1e9+7 的结果。

    数据范围
    0<N,V≤1000
    0<vi,wi≤1000

    解析:求最佳方案数需要一个数组 g ,在记录 f 数组同时更新 g 数组,最终遍历数组累计答案。
    Code:

    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N = 1010, MOD = 1e9+7, INF = 1e6;
    int f[N], g[N];         //f[i]:体积恰好是i时最大价值  g[i]:体积恰好是i时方案数
    int main()
    {
        for(int i=1;i<=N;i++)   f[i] = -INF;
        g[0] = 1;
        int n,V,maxw = 0;
        cin>>n>>V;
        for(int i=1;i<=n;i++)
        {
            int v,w;
            cin>>v>>w;
            for(int j=V;j>=v;j--)
            {
                int tp = max(f[j],f[j-v]+w);
                int s= 0;
                if(tp == f[j])  s += g[j];
                if(tp == f[j-v]+w)  s += g[j-v];
                if(s >= MOD)    s -= MOD;
                f[j] = tp;
                g[j] = s;
                maxw = max(maxw,f[j]);
            }
        }
        int ans = 0;
        for(int j=0;j<=V;j++)
        {
            if(maxw == f[j])
            {
                ans += g[j];
                if(ans >= MOD)  ans -= MOD;
            }
        }
        cout<<ans;
        return 0;
    }
    

    ps:博主能力有限,如果读者发现什么问题,欢迎私信或评论指出不足。欢迎读者询问问题,乐意尽我所能解答读者的问题。欢迎评论,欢迎交流。谢谢大家!

    展开全文
  • 动态规划背包问题

    2018-08-08 07:27:04
    动态规划背包问题 问题描述: 给定一个容量为N的背包,给定m件物品,每件物品价值为w[i]、重量为c[i],如何选择物体可以使物体的费用不超过背包的总容量,且背包能够带走的最大的价值。 1. 如果限定每件...
  • 动态规划背包问题 package Day08; import java.util.Arrays; import java.util.Random; import java.util.Scanner; public class T08_06 { /* * 动态规划 * 背包问题 * 一个背包可以装一定重量的物品在不...
  • 动态规划4 背包问题

    2020-04-03 10:45:48
    对于背包体积为W,物品数量是N,每个物品的体积是w[i],每个物品的价值是price[i]的选择,用这个背包装下的物品价值最大 dp[i][j]表示数量为i体积为j的时候选出的最大价值 方程:dp[i][j]=Math.max(dp[i-1][j],dp...
  • 01背包问题一、问题描述二、算法思路(动态规划)三、代码 一、问题描述 一个背包,体积是V,有n个物品,第i个物品的价值是v=vi,而第i个物品的体积是w=wi。 1、用这个背包最多可以装下的价值数? 2、哪些物品装进...
  • 对于背包问题在前面动态规划 - 0-1背包问题的算法优化已经讲到了关于0-1背包问题的解法,0-1背包问题是最基本的背包问题,它的特点是:每一件物品之多只能选择一件,即在背包中该物品数量只有0和1两种情况。...
  • 背包问题 动态规划

    2019-03-19 19:41:00
    问题简述 【题目描述】: 一个旅行者有一个最多能装M公斤的背包,现在有n件...=200)和N(物品数量N<=30) 第2至N+1行,每行两个整数,Wi,Ci,表示每个物品的重量和价值。 【输出格式】:仅一行,一个数,表...
  • 背包问题 一.0/1背包 题目描述  一个旅行者有一个最多能用 m 公斤的背包,现在有 n 件物品,它们的重量分别是 W1 ,W2 ,... , Wn ,它们的价值分别为 C1,C2 ,... ,Cn 。若每种物品只有一件旅行者能获得最大...
  • 对于物品X, 重量, 价值和背包总容量为以下数值的情况下, 背包容量限制下得到最大价值的物品组合方式 5个物品,(重量w,价值v)分别为:(5,12),(4,3),(7,10),(2,3),(6,6) 1. 假设最优答案 ...
  • 本算法用于背包问题动态规划算法,假设每种物品数量是不限的,最大体积为C时的所装最有价值物品
  • 考虑最一般形式的背包问题动态规划算法),如下: 输入一个整数W和V,W和V代表背包可容纳的最大重量和最大体积; 输入N个整数,代表N种物品;每个物品有4种属性,分别是重量、体积、价值、数量; 以下依次输入的N...
  • 一、01背包 ...第一行:两个整数,M(背包容量,M ≤ 200)和N(物品数量,N ≤ 30); 第2…N+1行:每行二个整数Wi,Ci,表示每个物品的重量和价值。 输出 仅一行,一个数,表示最大总价值。 样例输入 ...
  • 【题目描述】 ...=200)和NN(物品数量,N<=30N<=30); 第2…N+12…N+1行:每行二个整数Wi,CiWi,Ci,表示每个物品的重量和价值。 【输出】 仅一行,一个数,表示最大总价值。 【输入样例】 10
  • 动态规划问题-01背包

    2020-10-04 19:24:01
    动态规划问题01背包 题目描述 一个旅行者有一个最多能用m公斤的背包,现在有n件物品,它们的重量分别是W1,W2,…,Wn,它们的价值分别为C1,C2,…,Cn.若每种物品只有一件旅行者能获得最大总价值。 输入 第1行:两个...
  • 多重背包: 每种物品都有给定的数量,每种可拿物品不能超过本身固定的数量 超大背包: ---------01背包--------- 有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品所有挑选方案中...
  • 动态规划-01背包问题

    千次阅读 2018-05-22 13:08:28
    【题目名称】0/1背包一个旅行者有一个最多能装m公斤物品的背包,现在有n件物品,...=200)和n(物品数量,n&lt;=30)。第二~n+1行:每行两个整数wi,ci,表示每个物品的重量和价值【输出格式】一个数据,表示最大...
  • 背包问题就是类似这种给定容量最优解的问题,有很多种,这里说的是01背包问题。01背包:所有物品只有一个,只所以背包中任意物品的的数量只可能是0 或者 1。动态规划思路:当前情况的思考建立在之前的思...
  • 背包问题 【题目描述】 一个旅行者有一个最多能装 MM 公斤的背包,现在有 nn 件物品,它们的重量分别是W1,W2,…,WnW1,W2,…,Wn,它们的价值分别为C1,C2,…,CnC1,C2,…,Cn,旅行者能获得最大总价值。 【输入】 ...
  • 背包问题的个人理解(动态规划

    千次阅读 2018-08-12 13:45:17
    01背包问题描述:有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,每件物品数量只有一个,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?...
  • 0/1 背包问题 动态规划 有为N件物品,它们的重量w分别是w1,w2,…,wn,它们的价值v分别是v1,v2,…,vn,每件物品数量有且仅有一个,现在给你个承重为M的背包,背包里装入的物品具有的价值最大总和? 链接:...
  • 在N件物品取出若干件放在容量为W的背包里,每件物品的体积为W1,W2……Wn(Wi为...N为物品数量,W为背包的容量。(1 <= N <= 100,1 <= W <= 10000) 第2 - N + 1行,每行2个整数,Wi和Pi,分别是物品的...
  • 完全背包问题动态规划解法(普通的思路)

    万次阅读 多人点赞 2018-11-22 11:15:03
    有n个重量和价值分别为wi,vi的物品,从这些物品中挑选出总重量不超过W的物品所有挑选方案中价值总和的最大值 1≤n≤100 1≤wi,vi≤100 1≤W≤10000 输入: 第一行是n 第二行到是物品的重量 第三行是物品...
  • 动态规划 ---- python:简单背包问题

    千次阅读 2018-09-03 16:47:44
    1. 问题描述:有1 背包能装进4千克物体,吉他重1千克,价值1500;猫王音箱重4千克,价值3000;笔记本重3千克,价值2000,这个背包所能装的物体的最大价值。...对于背包问题,先解决子背包问题,再解决...
  • //最优解的值: int W = 17; //初始背包容量 int n = 5; //物品数量 int i; int w; int[] weight = { 3, 4, 7, 8, 9 }; //物品的重量 int[] v = {4, 5, 10
  • 用二维数组res[i][w]记录物品数量为i,背包容积为w时的最优值 对于第k个物品,需要判断当前背包的容量是否足够。 容量不够,则不能放入第k个物品(res[k][w] = res[k-1][w]) 容量足够,则取放或不放第k个物品时,...
  • 问题描述:   有n个重量和价值分别为wi,vi的... 在前面学习的基础上,其实这道题目并不难,首先普通的动规思路,在前面的01背包的基础上,因为物品数量是无限的,那么递推的思路就是这个物品可以选取0,1...n...

空空如也

空空如也

1 2 3
收藏数 59
精华内容 23
关键字:

动态规划背包问题求物品数量