关键词:
问题描述:
给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大??
在选择物品的时候,对每种物品i只有两种选择,即装入背包或不装入背包。不能讲物品i装入多次,也不能只装入物品的一部分。因此,该问题被称为0-1背包问题。
1 import java.math.BigInteger; 2 import java.util.Arrays; 3 import java.util.Scanner; 4 5 6 public class Main { 7 static int[][] b; 8 static int[] a; 9 static int[] a1; 10 static boolean[] flag; 11 public static void main(String[] args) { 12 Scanner input = new Scanner(System.in); 13 int n,m; 14 n = input.nextInt();//物品数量 15 m = input.nextInt();//背包大小 16 a = new int[n+1];//物品质量 17 a1 = new int[n+1];//物品价值 18 for(int i=1;i<=n;i++){ 19 a[i] = input.nextInt(); 20 } 21 for(int i=1;i<=n;i++){ 22 a1[i] = input.nextInt(); 23 } 24 b = new int[n+1][m+1];//物品数量价值表 25 flag = new boolean[n+1];//是否用过 26 for(int i=1;i<=n;i++){ 27 for(int j=1;j<=m;j++){ 28 //物品质量大于背包容量 29 if(j<a[i]){ 30 b[i][j] = b[i-1][j]; 31 //物品质量小于背包容量有两种情况 32 //1.物品不放入背包 33 //2.物品放入背包 34 }else{ 35 b[i][j] = Math.max(b[i-1][j], b[i-1][j-a[i]]+a1[i]); 36 } 37 } 38 39 } 40 //检测使用那些物品 41 int j = m; 42 for(int i=n;i>0;i--){ 43 if(b[i][j]>b[i-1][j]){ 44 flag[i] = true; 45 j = j-a[i]; 46 } 47 } 48 System.out.print("使用了:"); 49 for(int i=1;i<=n;i++){ 50 if(flag[i]) 51 System.out.print(i+" "); 52 } 53 System.out.println(); 54 System.out.println("最大值:"+b[n][m]); 55 } 56 57 }
背包问题(01背包,完全背包,多重背包)
...http://www.cnblogs.com/daoluanxiaozi/archive/2012/05/06/2486105.html 背包问题,经典有背包九讲。01背包 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些... 查看详情
01背包,完全背包,多重背包,混合背包
详见大牛背包九讲(下载地址:http://pan.baidu.com/s/1b9edXW)1//Class->物品种类,val->价值,room->所占空间,num->物品数量,Room->背包容量23#include<stdio.h>4constintmaxn=1e6;56intbag[maxn];7intRoom;89voidzero_one_bag( 查看详情
动态规划_01背包_完全背包_多重背包_分组背包(代码片段)
目录动态规划问题结题思路:模板题链接:01背包思路:代码:完全背包思路:代码多重背包思路:代码:组合背包思路:代码:动态规划问题结题思路:模板题链接:01背包模板题完全背包... 查看详情
01背包两维背包
#include<iostream>#include<algorithm>usingnamespacestd;/********************************01背包*/#defineN5#defineM12intvalue[N+1]={0,6,3,5,4,6};intweight[N+1]={0,2,2,6,5,4};//#defineN5//#defi 查看详情
动态规划之背包问题-01背包+完全背包+多重背包(代码片段)
01背包有n种不同的物品,每种物品分别有各自的体积v[i],价值 w[i] 现给一个容量为V的背包,问这个背包最多可装下多少价值的物品。1for(inti=1;i<=n;i++)2for(intj=V;j>=v[i];j--)3dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp[V]为所求完全背包0... 查看详情
动态规划背包问题01背包完全背包多重背包
一、01背包有N件物品和一个容量为V的背包。第i件物品的价格(即体积,下同)是w[i],价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。这是最基础的背包问题,总的来说就... 查看详情
动态规划-01背包
...,学长们很早之前就讲过了,然而我现在才来写。。。01背包01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。01背包题目的雏形是:有N件物品和一个容量为V的... 查看详情
01背包完全背包多重背包
参考(都有些错误):https://github.com/guanjunjian/Interview-Summary/blob/master/notes/algorithms/%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/01%E8%83%8C%E5%8C%85.mdhttps://blog.csdn.net/na_beginning/article/details/6 查看详情
9大背包第一弹|01背包
今天学习01背包。因为01背包在暑假学习过,所以上网看了一下文章,就能写出来了。主要还是一种动态规划的思想,设置背包的【容量】进行增长,【物品】进行增长。只要满足【当前物品】的【价值】=max{ ... 查看详情
01背包java实现(入门到精通)
一、什么是01背包 01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一... 查看详情
01背包+滚动数组
01背包定义:在$M$件物品取出若干件放在空间为$V$的背包里,每件物品的体积为$V_1$,$V_2$至$V_n$,与之相对应的价值为$W_1$,$W_2$至$W_n$。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。... 查看详情
01背包
问题描述:给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大??在选择物品的时候,对每种物品i只有两种选择,即装入背包或不... 查看详情
01背包+完全背包+多重背包+单调队列(代码片段)
01背包代码:逆序更新intn,m,f[105][N],dp[N];voidfun1()for(inti=1;i<=n;i++)//物品ifor(intj=1;j<=m;j++)//容量jif(j<w[i])f[i][j]=f[i-1][j];elsef[i][j]=max(f[i-1] 查看详情
01背包与完全背包
01背包有一个体积为V的背包,有n个物品,每个物品都有体积vi和价值wi,在背包体积范围内,求能桌下的最大价值。这个问题中每个物品只能用一次。设dp[i][j]表示用前i个物品装体积为j的背包。那么第i个物品要么装要么不装:1... 查看详情
背包问题(01背包)(代码片段)
--------开始-------- 每次用到背包问题就忘,今天特意把背包问题写下来,本篇只写01背包问题,至于其它的背包问题以后会陆续出现,大多数背包问题都是以01背包为原型来演变过来的,所以先介绍经典... 查看详情
01背包基础
TheaspiringRoytheRobberhasseenalotofAmericanmovies,andknowsthatthebadguysusuallygetscaughtintheend,oftenbecausetheybecometoogreedy.Hehasdecidedtoworkinthelucrativebusinessofbankrobberyonlyforashortwhi 查看详情
01背包问题和完全背包问题(代码片段)
...coder上面的题目中看到的这个问题,总结一下。先看01背包问题。01背包问题:一个背包总容量为V,现在有N个物品,第i个物品体积为weight[i],价值为value[i],现在往背包里面装东西,怎么装能使背包的... 查看详情
01完全多重背包模板
背包问题:背包总容量为W,有n件重量为weight[i],权值为value[i]的物品1、01背包:这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。1voidZeroOnePack(intweight,intvalue)2{3for(intw=W;w>=weight;w--)4dp[w]=max(dp[w-weight]+value,... 查看详情