洛谷P1858

\({\mathcal{For}}\) \({\mathcal{we}\ }\)\({\mathcal{live}\ }\)\({\mathcal{by}\ }\)\({\mathcal{faith}\ }\)\({\mathcal{,}\ }\)\({\mathcal{not}\ }\)\({\mathcal{by}\ }\)\({\mathcal{sight}\ }\)\({\mathcal{.}}\)

---

Description

N 种物品，有各自的价值 w 和代价 c；

一个背包，容量为 V；

背包内同样类型的物体只能装一个；

求 K 种不同的方法，使得背包在被装满的情况下价值和最大。

---

Analysis

01背包问题最 k 优解问题；

先考虑如何求最大解，运用 01 背包基础思想解决；

\(f[i]\) 表示当前背包装第 i 件物品的最大价值；

但显然这并不能满足这个题的需要

那~

• 开一个二维数组 \(f[i][j]\) 表示背包容量为 i 时的第 j 优解；

• 开两个变量 Yes 和 No 储存表示体积为 v 和 v - c[ ] 时的最优解；

• 开一个数组 Ans[ ] 来暂时存储答案；

• 开一个变量 cnt 记录当前是第 cnt 优解

方程式这里不好描述 ，具体见代码；

---

Code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#define maxn 2000100

#define maxm 4010

#define INF 0x3f3f3f3f

#define Init1(s) memset(s,0,sizeof s)

#define Init2(s) memset(s,INF,sizeof s)

#define Init3(s) memset(s,-INF,sizeof s)

using namespace std;

int k,v,n,w[maxn],c[maxn];

int f[maxm<<1][50];

int Res;

int Ans[maxm];

int cnt,Yes,No;

int read() {

	int 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<<1)+(s<<3)+ch-'0',ch=getchar();

	return s*w;

}

void Pack01(int cost,int weight) {

	for(int i=v; i>=weight; i--) {

		Yes=1;No=1;cnt=0;

		while(cnt<=k) {

			if(f[i][Yes]>f[i-weight][No]+cost) Ans[++cnt]=f[i][Yes++];

			else Ans[++cnt]=f[i-weight][No++]+cost;

		}

		for(int j=1; j<=k; j++) f[i][j]=Ans[j];

	}

}

int main() {

	Init3(f);

	f[0][1]=0;

	k=read(),v=read(),n=read();

	for(int i=1; i<=n; i++) {

		w[i]=read();

		c[i]=read();

		Pack01(c[i],w[i]);

	}

	for(int i=1; i<=k; i++) Res+=f[v][i];

	printf("%d\n",Res);

	return 0;

}

---