MyException - 我的异常网
当前位置:我的异常网» C语言 » 关于几个背包有关问题(C语言)

关于几个背包有关问题(C语言)

www.MyException.Cn  网友分享于:2013-08-09  浏览:0次
关于几个背包问题(C语言)

个人新学的几个背包问题,做下记录总结。(参考博客:http://blog.csdn.net/mu399/article/details/7722810  以及 http://blog.csdn.net/u013174702/article/details/45741395)

(1)01背包:

01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi,  f[i-1,j] }

f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。
Pi表示第i件物品的价值。该方程说白了就是比较放第i个和不放第i个物品两种决策,哪种决策价值大就选择哪种 。
我们举个例子来理解下:

假设f[i-1,j]表示我有一个承重为8的背包,当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值9,现在有个重量Wi为2 价值为Pi为6
的物品a,考虑是否放入承重为8的背包使其价值最大,f[i-1,j-Wi]代表一个承重为6的背包的最大价值(等于当前背包承重8减去物品a的重量2),
当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值为8
由于f[i-1][v-Wi]+w[i]= 9 + 6 = 15 大于f[i][v] = 8,所以物品a应该放入承重为8的背包。

总的来说:

方程之中,现在需要放置的是第i件物品,这件物品的重量是Wi,价值是Pi,因此f[i-1,j]代表的就是不将这件物品放入背包,而f[i-1],j-Wi]]+Pi则是代表将第i件放入背包之后的总价值,比较两者的价值,得出最大的价值存入现在的背包之中。

附上南阳oj上的一个题(49题):

 

开心的小明

 

时间限制:1000 ms  |  内存限制:65535 KB

 

难度:4

 

描述
小明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N 元钱就行”。今天一早小明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N 元。于是,他把每件物品规定了一个重要度,分为5 等:用整数1~5 表示,第5 等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N 元(可以等于N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v[j],重要度为w[j],共选中了k 件物品,编号依次为j1...jk,则所求的总和为:v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单.

 

输入
第一行输入一个整数N(0<N<=101)表示测试数据组数
每组测试数据输入的第1 行,为两个正整数,用一个空格隔开:
N m
(其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。)
从第2 行到第m+1 行,第j 行给出了编号为j-1
的物品的基本数据,每行有2 个非负整数
v p
(其中v 表示该物品的价格(v≤10000),p 表示该物品的重要度(1~5))
输出
每组测试数据输出只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的
最大值(<100000000)
样例输入
1
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
解决代码:
//01背包问题,开心的小明
#include<stdio.h>
#include<string.h>
#include<algorithm>  
using namespace std;
int dp[30001];//dp[i]表示质量为i时的最大价值
struct bag{
 int v;
 int p;
}a[26];
int main(){
int n;
scanf("%d",&n);
  while(n--){
  int N,m,i,j;
  scanf("%d%d",&N,&m);
  for(i=1;i<=m;i++)
  scanf("%d%d",&a[i].v,&a[i].p);
memset(dp,0,sizeof(dp));
  for(i=1;i<=m;i++){
    for(j=N;j>=a[i].v;j--){
    dp[j]=max(dp[j-a[i].v]+a[i].v*a[i].p,dp[j]);    
    }//确定要不要买价格为j的第i件物品,总是使dp的值最大
   }
 printf("%d\n",dp[N]);
  }    
}
(2)又见01背包:

又见01背包(通过南阳Oj一个例题来体现)

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
描述
    有n个重量和价值分别为wi 和 vi 的 物品,从这些物品中选择总重量不超过 W 
的物品,求所有挑选方案中物品价值总和的最大值。
  1 <= n <=100
  1 <= wi <= 10^7
  1 <= vi <= 100
  1 <= W <= 10^9
输入
多组测试数据。
每组测试数据第一行输入,n 和 W ,接下来有n行,每行输入两个数,代表第i个物品的wi 和 vi。
输出
满足题意的最大价值,每组测试数据占一行。
样例输入
4 5
2 3
1 2
3 4
2 2
样例输出
7
这题起初看以为就是普通的背包问题,仔细一看如果用dp[W]来表示质量为wi时的最大价值,因为W的范围太大开不了那么大的数组,
所以解决方法就是把价值和重量翻转,改用较小的价值来开数组,那么最后求的就是指定价值下的最小重量。
附上代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct bag{
  int w;
  int v;    
}a[101];
int dp[100000];
int main(){
int n,W;
while(scanf("%d%d",&n,&W)!=EOF){
int i,j,sum=0;

 for(i=0;i<n;i++){
 scanf("%d%d",&a[i].w,&a[i].v);    
 sum+=a[i].v;
 }
 for(i=0;i<=sum;i++)
 dp[i]=1e9;
 dp[0]=0;
 for(i=0;i<n;i++){
   for(j=sum;j>=a[i].v;j--){
       dp[j]=min(dp[j-a[i].v]+a[i].w,dp[j]);//dp[]代表指定价值下的最小重量,j为指定价值   
   }    
 }
 for(i=sum;i>=0;i--){//按顺序从大到小输出dp的值,即重量对应的价值
 if(dp[i]<=W){
 printf("%d\n",i);
 break;
 }
}
}
}

(3)完全背包:

完全背包(南阳oj311题)

时间限制:3000 ms  |  内存限制:65535 KB
难度:4
描述

直接说题意,完全背包定义有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。本题要求是背包恰好装满背包时,求出最大价值总和是多少。如果不能恰好装满背包,输出NO

输入
第一行: N 表示有多少组测试数据(N<7)。
接下来每组测试数据的第一行有两个整数M,V。 M表示物品种类的数目,V表示背包的总容量。(0<M<=2000,0<V<=50000)
接下来的M行每行有两个整数c,w分别表示每种物品的重量和价值(0<c<100000,0<w<100000)
输出
对应每组测试数据输出结果(如果能恰好装满背包,输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包,输出NO)
样例输入
2
1 5
2 2
2 5
2 2
5 1

代码:
#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[50005],c[2001],w[2001];    
int main(){
int N,M,V,i,j;
scanf("%d",&N);
while(N--){
scanf("%d%d",&M,&V);
for(i=1;i<=V;i++)
dp[i]=-1000000;
dp[0]=0;
for(i=0;i<M;i++)
scanf("%d%d",&c[i],&w[i]);
  for(i=0;i<M;i++){
      for(j=c[i];j<=V;j++){
      dp[j]=max(dp[j-c[i]]+w[i],dp[j]);
      }    
  }
 if(dp[V]<0)
 printf("NO\n");
 else
 printf("%d\n",dp[V]);
}    
}

解题思路:
0-1背包的状态转移方程是
for i = 1 to N
for v = V to Ci
F [v] = max{F [v],F [v Ci] + Wi}
完全背包就是不限制物品使用个数,可以无限使用,也就是可以重复放置一个物体
转移方程
for i = 1 to N
for v = Ci to V
F [v] = max(F [v], F [v Ci] + Wi)
你会发现,这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。 为什么这个算法就可行呢?首先想想为什么01背包中要按照v递减的次序来 循环。让v递减是为了保证第i次循环中的状态F [i, v]是由状态F [i 1, v Ci]递 推而来。换句话说,这正是为了保证每件物品只选一次,因为质量在减少不可能再能加入一个和原来质量一样大的物品,
而现在完全背包的特点恰是每种物品可选无限件,所以采用“质量增加”的循环,因此后面可能会继续加入和原来质量一样的物品。



 

文章评论

10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
总结2014中国互联网十大段子
总结2014中国互联网十大段子
老程序员的下场
老程序员的下场
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员应该关注的一些事儿
程序员应该关注的一些事儿
编程语言是女人
编程语言是女人
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员都该阅读的书
程序员都该阅读的书
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
 程序员的样子
程序员的样子
如何成为一名黑客
如何成为一名黑客
为什么程序员都是夜猫子
为什么程序员都是夜猫子
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
旅行,写作,编程
旅行,写作,编程
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
中美印日四国程序员比较
中美印日四国程序员比较
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员必看的十大电影
程序员必看的十大电影
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
那些争议最大的编程观点
那些争议最大的编程观点
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
10个调试和排错的小建议
10个调试和排错的小建议
我的丈夫是个程序员
我的丈夫是个程序员
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
代码女神横空出世
代码女神横空出世
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
鲜为人知的编程真相
鲜为人知的编程真相
程序员的鄙视链
程序员的鄙视链
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
每天工作4小时的程序员
每天工作4小时的程序员
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
Java程序员必看电影
Java程序员必看电影
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有