95 条题解
-
2
zrzluck99 LV 9 @ 2019-08-03 17:22:59
背包九讲里面的K大背包问题，每次维护一个长度为K的队列，求K优解时只要将两个队列进行归并即可。
复杂度 O(nmk)
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f /* --- Quick I/O --- */ template<class T> inline T Max(const T &x, const T &y){ return x>y?x:y; } template<class T> inline T Min(const T &x, const T &y){ return x<y?x:y; } inline ll read(){ ll s=0,w=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') w=-1; ch=getchar();} while (ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^'0'), ch=getchar(); return s*w; } void write(ll s){ if (s<0) s=-s,putchar('-'); if (s>9) write(s/10); putchar(s%10+'0'); } void writeln(ll s){ write(s); putchar('\n'); } void writeln(){ putchar('\n'); } int n,v,k; ll f[5012][55],w[233],c[233],tmp[55*2]; int main(){ ios::sync_with_stdio(false); k = read(); v = read(); n = read(); memset(f,-0x3f,sizeof(f)); f[0][1] = 0; for (int i=1;i<=n;i++) w[i] = read(), c[i] = read(); for (int i=1;i<=n;i++){ for (int j=v;j>=w[i];j--){ int p=1,q=1; for (int o=1;o<=k;o++){ if (f[j][p]>f[j-w[i]][q]+c[i]) tmp[o] = f[j][p++]; else tmp[o] = f[j-w[i]][q++]+c[i]; } for (int o=1;o<=k;o++) f[j][o] = tmp[o]; } } ll ans = 0; for (int i=1;i<=k;i++) ans += f[v][i]; writeln(ans); return 0; } -
1
最开始我想到的是DFS的做法，可惜复杂度实在是太高了。 （搜索O（2^N）, DPO（KVN））
之后还是看网上的解法，发现这道题居然是经典的 "K大背包" 问题。问题立即被简单解决，而它与普通背包的区别，也只是体现在了状态和转移上。状态：F[ i ][ j ]（表示装了i的体积下，第j优的情况）
转移：F[ i ][ 1 ] = max（F[ i ][ 1 ] , F[ i - W[ p ] ][ 1 ] + V[ p ] ） (特别情况)
F[ i ][ x ] 的转移来自 F[ i ][ y ] 或 F[ i - W[ p ] ][ z ] + V[ p ]
由于易知：
1. F[ i ][ h ] >= F[ i ][ h+1 ]
2. F[ i - W[ p ] ][ h ] + V[ p ] >= F[ i - W[ p ] ][ h+1 ] + V[ p ]
我们就可以分别维护 F[ i ][ y ] 和 F[ i - W[ p ] ][ z ] + V[ p ] 两种情况的转移值
用queue即可轻松实现 (类似归并排序的比较)DFS:(过前两点)
#include <map> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <bitset> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define INF (0x3f3f3f3f) #define LINF (0x3f3f3f3f3f3f3f3fLL) using namespace std; const int Nsize=205; struct GOOD { int v,w; bool operator < (const GOOD &x) const { return v>x.v; } }; int K,V,N; GOOD G[Nsize]; priority_queue<int> Q; void DFS (int f,int v,int s) { if (v==V) Q.push(s); if (f>N||v>=V) return; DFS(f+1,v+G[f].w,s+G[f].v); DFS(f+1,v,s); } int main () { cin>>K>>V>>N; for(int i=1;i<=N;i++) cin>>G[i].w>>G[i].v; sort(G+1,G+N+1); DFS(1,0,0); int ans=0; for(int i=1;i<=K;i++) { ans+=Q.top(); Q.pop(); } cout<<ans; return 0; }DP:
#include <map> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <bitset> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define INF (0x3f3f3f3f) #define LINF (0x3f3f3f3f3f3f3f3fLL) using namespace std; const int Ksize=55; const int Nsize=205; const int Msize=5005; int K,M,N; int W[Nsize],V[Nsize],F[Msize][Ksize]; queue<int> Q1,Q2; int main () { cin>>K>>M>>N; for(int i=1;i<=N;i++) cin>>W[i]>>V[i]; memset(F,-INF,sizeof(F)); F[0][1]=0; for(int i=1;i<=N;i++) for(int j=M;j>=W[i];j--) { for(int o=1;o<=K;o++) { Q1.push(F[j][o]); Q2.push(F[j-W[i]][o]+V[i]); } for(int o=1;o<=K;o++) if (Q1.front()>Q2.front()) { F[j][o]=Q1.front(); Q1.pop(); } else { F[j][o]=Q2.front(); Q2.pop(); } while(!Q1.empty()) Q1.pop(); while(!Q2.empty()) Q2.pop(); } int ans=0; for(int i=1;i<=K;i++) ans+=F[M][i]; cout<<ans; return 0; } -
1
jerryzheng2005 LV 10 @ 2017-04-09 18:51:31
//p1412 #include<iostream> #include<vector> #include<algorithm> using namespace std; int k,v,n,w[201],p[201]; vector<int> f[5001]; int main() { int i,j,sum; cin>>k>>v>>n; for (i=1;i<=n;i++) cin>>w[i]>>p[i]; f[0].push_back(0); push_heap(f[0].begin(),f[0].end(),greater<int>()); for (i=1;i<=n;i++) for (j=v;j>=w[i];j--) for (int kk=0;kk<f[j-w[i]].size();kk++) { if (f[j].size()<k) { f[j].push_back(f[j-w[i]][kk]+p[i]); push_heap(f[j].begin(),f[j].end(),greater<int>()); } else { if (f[j-w[i]][kk]+p[i]>f[j].front()) { pop_heap(f[j].begin(),f[j].end(),greater<int>()); f[j].pop_back(); f[j].push_back(f[j-w[i]][kk]+p[i]); push_heap(f[j].begin(),f[j].end(),greater<int>()); } } } sum=0; for (i=0;i<f[v].size();i++) sum+=f[v][i]; cout<<sum<<endl; return 0; } -
0
//一个简洁的归并代码
//不解释qwq
#include<bits/stdc++.h>
using namespace std;int c[205], p[205], f[5005][55];
int main()
{
memset(f, 0x8f, sizeof(f));
int k, v, n;
cin>>k>>v>>n;
for(int i=1;i<=n;i++) scanf("%d%d", &c[i], &p[i]);
f[0][1]=0;
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=v;j>=c[i];j--){
int arr[55], iter=1, a=1, b=1;
memset(arr, 0x8f, sizeof(arr));
while(iter<=k){
if(a>f[j][0]&&b>f[j-c[i]][0]) //两数组都用完了
break;
if(a>f[j][0]||(b<=f[j-c[i]][0]&&f[j][a]<f[j-c[i]][b]+p[i]))//分类讨论
arr[iter]=f[j-c[i]][b++]+p[i];
else
arr[iter]=f[j][a++];
iter++;
}
for(int l=1;l<iter;l++) f[j][l]=arr[l];
f[j][0]=iter-1;
}
int ans=0;
for(int i=1;i<=k;i++)
ans+=f[v][i];
cout<<ans<<endl;
return 0;
} -
0
注意到题目所求的是前k大的方案，直接在DP时归并即可。可以使用
std::inplace_merge()#include <bits/stdc++.h> using namespace std; int dp[5001][101]; const int INF=0x3f3f3f3f; int main(){ int k,v,n; scanf("%d%d%d",&k,&v,&n); for(int i=0;i<=v;i++) for(int j=1;j<=k;j++) dp[i][j]=-INF; dp[0][1]=0; while(n--){ int x,y; scanf("%d%d",&x,&y); for(int i=v;i>=x;i--){ for(int j=1;j<=k;j++) dp[i][j+k]=dp[i-x][j]+y; inplace_merge(dp[i]+1,dp[i]+k+1,dp[i]+2*k+1,greater<int>()); } } int ans=0; for(int i=1;i<=k;i++) ans+=dp[v][i]; printf("%d",ans); } -
0
编译成功
测试数据 #0: Accepted, time = 15 ms, mem = 4716 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4716 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 4716 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 4716 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 4716 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 4716 KiB, score = 20
测试数据 #6: Accepted, time = 78 ms, mem = 4716 KiB, score = 30
Accepted, time = 184 ms, mem = 4716 KiB, score = 100终于过了，因为这道题才去看了背包九讲和归并排序。这道题一开始一直没想到的就是那个【每个背包必须填满】的条件，看了看题解发现可以把dp数组赋值负数代表无法填满，这样一来只要dp数组对应的值是正数那么这个结果就一定是正确的了。。。。
#include<iostream> #include<cstring> #include<vector> #include<sstream> #include<algorithm> #include<string> #include<cstdio> #include<math.h> #include<cctype> #include<vector> #define maxn 5005 using namespace std; int K, V, N; int dp[maxn][210], v[maxn], p[maxn], a[210], b[210]; int main() { cin >> K >> V >> N; for (int i = 1; i <= N; i += 1) cin >> v[i] >> p[i]; for (int i = 0; i <= V; i++) for (int j = 1; j <= K; j++) dp[i][j] = -maxn; dp[0][1] = 0; a[K + 1] = b[K + 1] = -1; for (int i = 1; i <=N; i += 1){ for (int j = V; j >= v[i]; j -= 1) { if (dp[j - v[i]][1] > -1){ for (int k = 1; k <= K; k += 1){ a[k] = dp[j][k]; b[k] = dp[j - v[i]][k] + p[i]; } int cur = 1, ca = 1, cb = 1; while (cur <= K && (a[ca] != -1 || a[cb] != -1)){ if (a[ca] > b[cb]){ dp[j][cur] = a[ca]; ca += 1; } else{ dp[j][cur] = b[cb]; cb += 1; } /*if (dp[j][cur] != dp[j][cur - 1])*/ //仍然想不通为什么不能判重 cur += 1; } } } } int ans = 0; for (int i = 1; i <= K; i += 1) ans += dp[V][i]; cout << ans << endl; /*system("pause");*/ return 0; } -
0
-
0
type re=record v,w:longint; end; var n,m,z,i,j,k:longint; ans:int64; a:array[0..200]of re; g1,g2:array[0..50]of int64; f:array[0..5000,0..50]of int64; function max(x,y:int64):int64; begin if x>y then exit(x) else exit(y); end; procedure Init; var i:longint; begin readln(z,m,n); for i:=1 to n do read(a[i].w,a[i].v); end; procedure merger(w:longint); var i,j,tot:longint; begin for i:=1 to z do g2[i]:=f[w][i]; i:=1; j:=1; tot:=0; while tot<=z do begin inc(tot); if g1[i]>g2[j] then begin f[w][tot]:=g1[i]; inc(i); end else begin f[w][tot]:=g2[j]; inc(j); end; end; end; procedure Main; var i,j,k:longint; begin for j:=1 to m do for k:=1 to z do f[j][k]:=-(1<<62); for i:=1 to n do for j:=m downto a[i].w do begin for k:=1 to z do g1[k]:=-(1<<62); for k:=1 to z do begin g1[k]:=f[j-a[i].w][k]+a[i].v; if j-a[i].w=0 then break; end; merger(j); end; end; procedure print; var i:longint; begin for i:=1 to z do ans:=ans+max(0,f[m][i]); writeln(ans); end; begin Init; Main; Print; end. -
0
#include<cstdio> #include<iostream> using namespace std; const int maxK=50+5,maxV=5000+5,maxN=200+5,INF=0x7F7F7F7F; int K,V,N,q1,q2,a1,a2; int f[maxV][maxK],T[maxK]; void merge(int*,int*,int); int main() { int v,a,ans=0; scanf("%d %d %d",&K,&V,&N); for(int i=0;i<=V;i++) for(int j=1;j<=K;j++) f[i][j]=-INF; f[0][1]=0; for(int i=1;i<=N;i++) { scanf("%d %d",&v,&a); for(int j=V;j>=v;j--) if(f[j-v][1]>-1) merge(f[j],f[j-v],a); } for(int i=1;i<=K;i++) ans+=f[V][i]; printf("%d\n",ans); return 0; } void merge(int* A,int* B,int C) { q1=1,q2=1; for(int i=1;i<=K;i++) { a1=A[q1],a2=B[q2]+C; if(a1<a2) T[i]=a2,q2++; else T[i]=a1,q1++; } for(int i=1;i<=K;i++) A[i]=T[i]; }01背包+多路归并
-
0
这...必须纪念一下！
感谢**Vijos**；
感谢**zengzhen1002**；
感谢**DD_engi**；
Vijos AC126~
测试数据 #0: Accepted, time = 0 ms, mem = 1824 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1824 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1824 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 1828 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1820 KiB, score = 10
测试数据 #5: Accepted, time = 156 ms, mem = 1824 KiB, score = 20
测试数据 #6: Accepted, time = 203 ms, mem = 1824 KiB, score = 30
Accepted, time = 420 ms, mem = 1828 KiB, score = 100
# <Pascal Code>
pascal
type int=longint;
var
k,v,n,i,j,l,ans,x1,x2:int;
a,b:array[0..201]of int;
f:array[0..5001,0..51]of int;
q1,q2:array[0..101]of int;
begin
readln(k,v,n);
for i:=1 to n do readln(a[i],b[i]);
for i:=0 to 5001 do
for j:=0 to 51 do f[i,j]:=-maxlongint div 2;
f[0,1]:=0;
for i:=1 to n do
for j:=v downto a[i] do
if f[j-a[i],1]>-1 then
begin
fillchar(q1,sizeof(q1),0);
fillchar(q2,sizeof(q2),0);
x1:=1; x2:=1;
for l:=1 to k do
begin
q1[l]:=f[j-a[i],l]+b[i];
q2[l]:=f[j,l];
if q1[x1]>=q2[x2] then
begin
f[j,l]:=q1[x1];
inc(x1);
end else
begin
f[j,l]:=q2[x2];
inc(x2);
end;
end;
end;
ans:=0;
for i:=1 to k do ans:=ans+f[i];
writeln(ans);
end.
如果奇迹有颜色，那么一定是**橙色！** -
0
wang_yanheng LV 10 @ 2015-11-15 12:06:33
本题其实是求01背包的前k优解之和，归并一下就好
f[i][j] 表示容量为 i 时第 j 优解的值
关于题目中所述的“背包必须装满”可以这样处理：把数组全部赋 -INF，特殊的是 f[0][0] = 0，这样一来最后
f[capacity][1..k] 中的负数取值就意味着无法装满。具体见代码。#include <stdio.h>
#include <limits.h>int values[300];
int costs[300];
int f[5001][51];void merge(int to, int from, int value, int size){
int tmp[105];
int i = 0, j = 0, k = 0;
while(i < size && j < size){
if(f[to][i] > f[from][j]+value)
tmp[k++] = f[to][i++];
else
tmp[k++] = f[from][j++]+value;
}
while(i < size)
tmp[k++] = f[to][i++];
while(j < size)
tmp[k++] = f[from][j++]+value;
for(i=0; i<size; i++)
f[to][i] = tmp[i];
}
int main(){
int numPack, numThing, capacity;
int i, j;
scanf("%d %d %d", &numPack, &capacity, &numThing);
for(i=0; i<numThing; i++)
scanf("%d %d", &costs[i], &values[i]);
for(i=0; i<=capacity; i++){
for(j=0; j<=numPack; j++)
f[i][j] = LONG_MIN;
}
f[0][0] = 0;
for(i=0; i<numThing; i++){
for(j=capacity; j>=costs[i]; j--)
merge(j, j-costs[i], values[i], numPack);
}
j = 0;
for(i=0; i<numPack && f[capacity][i]>=0; i++)
j += f[capacity][i];
printf("%d\n", j);
return 0;
} -
0
评测结果
编译成功Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(1,5) Note: Local variable "m" not used
Linking foo.exe
47 lines compiled, 0.1 sec , 28624 bytes code, 1628 bytes data
1 note(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 1580 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1576 KiB, score = 10
测试数据 #2: Accepted, time = 2 ms, mem = 1576 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 1572 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1572 KiB, score = 10
测试数据 #5: Accepted, time = 265 ms, mem = 1576 KiB, score = 20
测试数据 #6: Accepted, time = 218 ms, mem = 1572 KiB, score = 30
Accepted, time = 593 ms, mem = 1580 KiB, score = 100 -
0
program p1412;
var
w,c:array[1..200] of longint;
opt:array[0..50,0..5000] of longint;
n,v,k:longint;
procedure init;
var
i:longint;
begin
fillchar(opt,sizeof(opt),0);
readln(k,v,n);
for i:=1 to n do
read(w[i],c[i]);
opt[0,0]:=1;
end;
procedure solve;
var
i,j,e,t,temp,s,x:longint;
begin
for i:=1 to n do
for j:=v downto w[i] do
begin
for s:=1 to opt[0,j-w[i]] do
begin
if opt[0,j]+1<=k then opt[0,j]:=opt[0,j]+1;
if opt[s,j-w[i]]+c[i]>opt[opt[0,j],j] then
begin
opt[opt[0,j],j]:=opt[s,j-w[i]]+c[i];
x:=opt[0,j]-1;
for e:=x downto 1 do
if opt[e,j]<opt[e+1,j] then
begin
temp:=opt[e,j];
opt[e,j]:=opt[e+1,j];
opt[e+1,j]:=temp;
end;
end;
end;
end;
end;
procedure shuchu;
var
i,ans:longint;
begin
ans:=0;
for i:=1 to k do
ans:=ans+opt[i,v];
writeln(ans);
end;
begin
init;
solve;
shuchu;
end. -
0
var
F:Array[0..5000,1..40] of longint; //VIJOS1412
n,m,v,i,j,k,temp,c,w,p,ans:Longint;begin
readln(n,v,m);
fillchar(f,sizeof(f),-1);
f[0][1]:=0;
for i:=1 to m do
begin
read(c,w);
for j:=v downto c do
for k:=n downto 1 do
if f[j-c][k]-1 then
begin
temp:=F[j-c][k]+w;
if temp>F[j][n] then
begin
F[j][n]:=temp;
p:=n;
while (F[j][p]>F[j][p-1]) and (p>=2) do
begin
temp:=F[j][p];
F[j][p]:=F[j][p-1];
F[j][p-1]:=temp;
dec(p)
end
end
end
end;
writeln(ans)
end. -
0
STL就是慢...
#include
#include
#include
#include
using namespace std;bool cmp(int &a,int &b)
{
if ( a>b ) return true;
return false;
}struct heap
{
vector data;void push(int t)
{
data.push_back(t);
push_heap( data.begin(), data.end(),cmp );
}void pop(void)
{
pop_heap( data.begin(), data.end(),cmp );
data.pop_back();
}int top(void) { return data.front(); }
int size(void) { return data.size(); }
};#define maxn 201
#define maxv 5001long W[maxn],P[maxn],N,K,V,Ans;
heap D[maxv];int main(void)
{
long i,j,k;
cin>>K>>V>>N;
for ( i=1;i>W[i]>>P[i];
D[0].push(0);
for ( j=1;j-1;i-- )
if ( i-W[j]>=0 && D[i-W[j]].size() )
for ( k=0;kD[i].top() )
{
D[i].pop();
D[i].push(x+P[j]);
}else if ( D[i].size() -
0
guori12321 LV 8 @ 2009-11-03 20:04:04
感谢1S的题解！
看了我一个多小时，总算明白了。做完以后又发现很水，于是又感叹这一个小时浪费了。。。
zrzluck99
LV 9
@ 2019-08-03 17:22:59
