关于几个背包问题

2019-09-03 03:12 来源:未知

Openjudge 百练第4109题,openjudge4109题

 1 # -*- coding:utf-8 -*-
 2 
 3 def set_1(i, q):
 4     ''' generate a i*i ARRAY for all relationships
 5     if there is a relation set 1 or 0
 6     return i*i ARRAY with 1 or 0
 7     '''
 8     a = [0 for i in range(i*i)] 
 9     for j in range(len(q)):
10         n, m = q[j]
11         a[(n-1)*i+(m-1)] = 1
12         a[(m-1)*i+(n-1)] = 1
13     return a 
14     
15 def solve(i, q, r):
16     ''' solve question
17     i is the number of people 
18     q is the set of questions
19     r is the set of relationships, the result of function set_1(); 
20     '''
21     result = 0
22     for j in range(len(r)):
23         n, m = r[j]
24         for l in range(i):
25             if q[(n-1)*i+l] == 1 and q[(m-1)*i+l] == 1:
26                 result += 1
27         print(result)
28         result = 0
29         
30 def main():
31     d = [ 3, [3,2,2],
32              [1,3],
33              [2,3],
34              [1,2],
35              [1,3],
36              [4,3,2],
37              [1,2],
38              [2,3],
39              [1,4],
40              [2,4],
41              [1,3],
42              [5,2,1],
43              [1,2],
44              [1,4],
45              [3,4]
46         ]
47     for x in d:                         #Dispaly input 
48         print(x)
49     
50     loc = []
51     for m in range(1,len(d)):           #Get the index of every question  
52         if len(d[m])==3:
53             loc.append(m)
54 
55     for i in range(len(loc)):           #Sovle each question
56         pNum, qNum, aNum = d[loc[i]]    #slice out R and Q in d[]
57         t = loc[i]+1
58         R = d[t:t+qNum]
59         Q = d[t+qNum:t+qNum+aNum]       
60             
61         r_1 = set_1(pNum,R)             # set 1 for question
62         print('-------------------nCase'+str(i+1)+':')
63         solve(pNum, r_1, Q)
64             
65 if __name__=='__main__':
66     main()
67     
68 '''OUTPUT
69 3
70 [3, 2, 2]
71 [1, 3]
72 [2, 3]
73 [1, 2]
74 [1, 3]
75 [4, 3, 2]
76 [1, 2]
77 [2, 3]
78 [1, 4]
79 [2, 4]
80 [1, 3]
81 [5, 2, 1]
82 [1, 2]
83 [1, 4]
84 [3, 4]
85 -------------------
86 Case1:
87 1
88 0
89 -------------------
90 Case2:
91 1
92 1
93 -------------------
94 Case3:
95 0
96 '''

 

在OpenJudge见到二个主题素材:

描述

小明和小红去参加party。开会地点香港中华总商会共有n个人,那么些人西藏中国广播公司大朋友关系,有的则互相不认得。朋友关系是相互的,即如若A是B的敌人,那么B也是A的对象。小明和小红想清楚里面某多个人有个别许个集体的朋友。 

输入第一行事二个正整数c,代表测验数据的个数。接下来是c组测验数据。

对此每组测量试验数据,第一行是八个数字n(2<=n<=100),m和k,分别代表会议厅中的人数,已知的相恋的人关周密据,难题的数量。接下来的m行,每行用八个数字i和j(1<=i,j<=n)表示了二个情侣关系,表示第i民用和第j民用是有相爱的人关系。接下来的k行,每行用七个数字i和j(1<=i,j<=n)表示二个标题,请问第i私人商品房和第j私有有稍许公共的意中人。输出对于第i组测验数据,首先输出一行”Case i:”,接下去得k行代表了k个难题,每行输出第i民用和第j私家有多少公共的爱侣。

百练第4109题,openjudge4109题 1 # -*- coding:utf-8 -*- 2 3 def set_1(i, q): 4 ''' generate a i*i ARRAY for all relationships 5 if there is a relation set 1 or 0 6 r...

私家新学的多少个信封包难题,做下记录总括。(参考博客:  以及

(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题):

 

开心的小明

 

岁月范围:一千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(<两千0)表示总钱数,m(<25)为期待购进物品的个数。)
从第2 行到第m+1 行,第j 行给出了编号为j-1
的货物的骨干数据,每行有2 个非负整数
v p
(个中v 表示该货品的标价(v≤一千0),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("%dn",dp[N]); 
  }    
}
(2)又见01背包:

又见01手拿包(通过德阳Oj贰个例题来反映)

时刻范围:一千 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("%dn",i);
 break;
 }
}
}
} 
(3)完全背包:

一心手包(南阳oj311题)

日子范围:三千ms  |  内部存储器限制:65535 KB

难度:4

描述
一向说题意,完全单肩包定义有N种物品和二个体积为V的公文包,每个物品都有Infiniti件可用。第i种物品的容量是c,价值是w。求解将怎么着货品装入单肩包可使这么些物料的体量总和不超越背兼体量,且价值总和最大。本题要求是手提包恰好装满双肩包时,求出最大价值总和是有一些。假使不可能正好装满信封包,输出NO

输入
先是行: N 代表有多少组测验数据(N<7)。
接下去每组测验数据的首先行有四个整数M,V。 M代表物品类别的多寡,V表示托特包的总体量。(0<M<=3000,0<V<=四千0)
接下去的M行每行有七个整数c,w分别代表每个货品的分量和价值(0<c<一千00,0<w<一千00)

输出
对应每组测量试验数据输出结果(假设能正好装满手提包,输出装满单肩包时包包内货物的最大价值总和。 即使不能够正好装满手提袋,输出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("NOn");
 else
 printf("%dn",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]递
推而来。换句话说,这正是为了保证每件物品只选一次,因为质量在减少不可能再能加入一个和原来质量一样大的物品,
而现在完全背包的特点恰是每种物品可选无限件,所以采用“质量增加”的循环,因此后面可能会继续加入和原来质量一样的物品。。

 

TAG标签:
版权声明:本文由990888藏宝阁发布于编程算法,转载请注明出处:关于几个背包问题