184 条题解
-
5
浮光过客 LV 10 @ 2015-10-08 19:58:44
将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附
件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的
一个附件集合组成。
按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用
的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附
件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策
略。事实上，设有n个附件，则策略有2n + 1个，为指数级。
10
考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所
以一个主件和它的附件集合实际上对应于6中的一个物品组，每个选择了主件又
选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是
这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，
因为物品组中的物品还是像原问题的策略一样多。
再考虑对每组内的物品应用2.3中的优化。我们可以想到，对于第k个物品组
中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，可
以对主件k的“附件集合”先进行一次01背包，得到费用依次为0: : :V Ck所
有这些值时相应的最大价值Fk[0 : : : V Ck]。那么，这个主件及它的附件集合
相当于V Ck + 1个物品的物品组，其中费用为v的物品的价值为Fk[v Ck] +
Wk，v的取值范围是Ck v V 。
也就是说，原来指数级的策略中，有很多策略都是冗余的，，通过一次01背包
后，将主件k及其附件转化为V Ck + 1个物品的物品组，就可以直接应用6的
算法解决问题了。-
背包九讲万岁~！~！~！~！~！~
-
虽然我不会做==-
-
2859198007 @ 2015-10-22 21:24:20
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<fstream>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M;
struct node{
int v,p,q,c;
}th[100];
int f[100][32001];//f[i][j]第i组的附件组成价值为j的最优解
int a[100][100];
int root[100];
int tot;//总组数
int ans[32001];
int main(){
N=read(); M=read();
for(int i=1;i<=M;i++){
th[i].v=read(); th[i].p=read(); th[i].q=read();
th[i].c=th[i].p*th[i].v;//计算出物品的价值
}
for(int i=1;i<=M;i++){
if(th[i].q!=0){
int now=th[i].q;//所属的主件物品编号
int tmp=++a[now][0];//主件的附件个数
a[now][tmp]=i;
}
else{
tot++;//主件个数加一
root[tot]=i;
}
}
//01背包
for(int i=1;i<=tot;i++){//枚举主件
int zhu=root[i];
for(int j=1;j<=a[zhu][0];j++){//枚举该主件的附件
for(int v=N;v>=0;v--){//钱
int temp=a[zhu][j];
int jian=th[temp].v;
int jia=th[temp].c;
if(v>=jian){
f[zhu][v]=max(f[zhu][v],f[zhu][v-jian]+jia);
}
}
}
}
//分组背包
for(int i=1;i<=tot;i++){
int zhu=root[i];
for(int v=N;v>=0;v--){
for(int k=0;k<=N;k++){
if(v-k-th[zhu].v>=0){
ans[v]=max(ans[v],ans[v-k-th[zhu].v]+f[zhu][k]+th[zhu].c);
}
}
}
}
cout<<ans[N];
return 0;
} -
'FYJ @ 2017-12-08 20:21:07
@2859198007: 可以把数组的意思注释一下吗
-
-
3
#include<cstdio> #include<iostream> int dp[33000], w[70], p[70], q[33000][3], zf[33000], fa; int main() { int v, n; scanf("%d%d", &v, &n); for(int i=1; i<=n; i++) { scanf("%d%d%d", &w[i], &p[i], &fa); p[i]*=w[i]; if(fa!=0) { zf[i]=1; if(q[fa][1]==0) q[fa][1]=i; else q[fa][2]=i; } } for(int i=1; i<=n; i++) for(int j=v; j>=w[i]; j--) if(zf[i]==0) { dp[j]=std::max(dp[j],dp[j-w[i]]+p[i]); if(w[i]+w[q[i][1]]<=j) dp[j]=std::max(dp[j], dp[j-w[i]-w[q[i][1]]]+p[i]+p[q[i][1]]); if(w[i]+w[q[i][2]]<=j) dp[j]=std::max(dp[j], dp[j-w[i]-w[q[i][2]]]+p[i]+p[q[i][2]]); if(w[i]+w[q[i][1]]+w[q[i][2]]<=j) dp[j]=std::max(dp[j], dp[j-w[i]-w[q[i][1]]-w[q[i][2]]]+p[i]+p[q[i][1]]+p[q[i][2]]); } printf("%d", dp[v]); return 0; } -
3
Var n,m,i,j:longint; v,w:array[1..1000,1..3]of longint; c,f,z:array[-32000..32000]of longint; Function max(x,y:longint):longint; Begin if x>y then exit(x); exit(y); End; Begin readln(n,m); for i:=1 to m do begin c[i]:=1; readln(v[i,1],w[i,1],z[i]); end; for i:=1 to m do if z[i]>0 then begin inc(c[z[i]]); v[z[i],c[z[i]]]:=v[i,1]; w[z[i],c[z[i]]]:=w[i,1]; end; for i:=1 to m do for j:=n downto 1 do if z[i]=0 then begin f[j]:=max(f[j-1],f[j]); if v[i,1]<=j then f[j]:=max(f[j-v[i,1]]+v[i,1]*w[i,1],f[j]); if v[i,1]+v[i,2]<=j then f[j]:=max(f[j-v[i,1]-v[i,2]]+v[i,1]*w[i,1]+v[i,2]*w[i,2],f[j]); if v[i,1]+v[i,2]+v[i,3]<=j then f[j]:=max(f[j-v[i,1]-v[i,2]-v[i,3]]+v[i,1]*w[i,1]+v[i,2]*w[i,2]+v[i,3]*w[i,3],f[j]); end; writeln(f[n]); readln; End.这个直接背包然后枚举四种情况，然后一个一个 枚举，
四种情况分别是：
一个都不取
取主件
取主件 和一个附件
取主件和俩个附件
一一枚举就好了-
xieshihua @ 2017-12-06 22:43:13
是五种情况吧
还有取主件和另一个附件
-
-
1
对于每一个主件处理出的情况，在 n-v[k]+1n−v[k]+1 种情况之中只能最多选择一种选入最终答案之中（把上面文字多读几遍吧），原问题便转化成一个分组背包问题。
如果你不知道分组背包的话：
for 所有的组k
for v = V ... 0
for 所有的i属于组k
f[v]=max{f[v],f[v-c[i]]+w[i]}
这题的分组背包部分应该是这样写的：
for 所有的主件数k
for j = n ... 0
for 所有的主件和附件的组合属于组k
f[j]=max{f[j],f[j-v[i]]+v[i]*p[i]}
上面就已经是具体思路了，实现需要比较多的数组存储结果，还有最容易错的一点是，本题的情况状态01背包计算需要使用 “恰好背包” （数组下标严格与花费价钱相等，详见代码注释）：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct cas
{
int v,p,q;
}a[60],pat[60][60];
int n,m,t[60],V[60][10],P[60][10],cnt[60],f[32000],ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);//正常的读入
if(a[i].q)//如果这个物品是附件
{
t[a[i].q]++;
pat[a[i].q][t[a[i].q]].v=a[i].v;
pat[a[i].q][t[a[i].q]].p=a[i].p;
pat[a[i].q][t[a[i].q]].q=a[i].q;//把它存在相应的主件的分组中
}
}
for(int i=1;i<=m;i++)//01背包处理
{
if(t[i])//如果当前物品为主件
{
memset(f,-1,sizeof(f));//恰好背包的处理，-1表示不恰好取到此价值
f[0]=0;//恰好背包的处理
for(int j=1;j<=t[i];j++)
for(int k=n-a[i].v;k>=pat[i][j].v;k--)
if(f[k]<f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p && f[k-pat[i][j].v]!=-1)//恰好背包的判断
f[k]=f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p;//很平常的01状态转移
for(int j=0;j<=n-a[i].v;j++)
if(f[j]!=-1)//恰好背包的判断，这种附件组合满足题意
{
cnt[i]++;
V[i][cnt[i]]=j+a[i].v;
P[i][cnt[i]]=f[j]+a[i].v*a[i].p;//把此情况存在主件i的分组中，为分组背包做好处理
}
}
if(!a[i].q)//只买主件
{
cnt[i]++;
V[i][cnt[i]]=a[i].v;
P[i][cnt[i]]=a[i].v*a[i].p;//存储
}
}
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)
for(int j=n;j>=0;j--)
for(int k=1;k<=cnt[i];k++)
if(j>=V[i][k])
f[j]=max(f[j],f[j-V[i][k]]+P[i][k]);//分组背包的计算
for(int i=0;i<=n;i++)
ans=max(ans,f[i]);
printf("%d",ans);//输出
return 0;
} -
1
01背包变形，主要是处理好主从的关系，个人在输入数据的时候把主件和附件放在一起，然后循环每个主件，讨论5种情况（不买主件、仅买主件、买主件和第一附件、买主件和第二附件、买主件和两附件）选最大值，优化到一维数组。
#include<iostream> #include<algorithm> using namespace std; int major[60],mNum=0,V[180],P[180],v,p,q,N,m,index,f[32100]; int main(){ cin>>N>>m; for(int i=0;i<m;i++){ cin>>v>>p>>q; if(q==0){//主件 index=i*3; major[mNum++]=index; }else{//附件数据放到主件后 index=(q-1)*3+1;//对应主件位置+1 if(P[index]>0)//已有一个附件 index++; } V[index]=v; P[index]=p; } for(int i=0;i<mNum;i++){//遍历每一个主件 index=major[i];//取主件序号 for(int j=N;j>=V[index];j--){ int rest=j-V[index];//买主件后剩余钱 int mV=V[index]*P[index];//主件价格与重要度乘积 int cmp[5]={f[j],f[rest]+mV};//不买/仅买主件 if(P[index+1]>0){//有附件 int rest1=rest-V[index+1];//买第一附件后剩余钱 if(rest1>=0)//买得起第一附件 cmp[2]=f[rest1]+mV+V[index+1]*P[index+1];//买主件和第一附件 if(P[index+2]>0){//有第二附件 int rest2=rest-V[index+2];//买第二附件后剩余钱 if(rest2>=0){//买得起第二附件 cmp[3]=f[rest2]+mV+V[index+2]*P[index+2];//买主件和第二附件 int rest12=rest1-V[index+2];//买两附件后剩余钱 if(rest12>=0)//买得起两附件 cmp[4]=f[rest12]+mV+V[index+1]*P[index+1]+V[index+2]*P[index+2];//买主件和两附件 } } } f[j]=*max_element(cmp,cmp+5); } } cout<<f[N]<<endl; return 0; } -
1
将输入处理一下，将附件和对应的主件放在一起，可以简化问题。
#include<bits/stdc++.h> using namespace std; int N,m,tv,tp,tq,v[250],p[250],a[250][32000]; int dp(int i,int j){ int &ans = a[i][j]; if(ans) return ans; if(i==0) return 0; if(j>=v[i]&&v[i]!=0){ if(i%4==0) ans = max(dp(i-4,j),dp(i-1,j-v[i])+v[i]*p[i]); else ans = max(dp(i-1,j),dp(i-1,j-v[i])+v[i]*p[i]); }else{ if(i%4==0) ans = dp(i-4,j); else ans = dp(i-1,j); } return ans; } int main(){ scanf("%d%d",&N,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&tv,&tp,&tq); if(tq==0){ v[i*4] = tv; p[i*4] = tp; } else{ int cur = tq*4-1; while(v[cur]) cur--; v[cur] = tv; p[cur] = tp; } } printf("%d",dp(m*4,N)); } -
1
#include <iostream> #include <algorithm> using namespace std; int N, m;//N总钱数，m物品件数 long long v[60], w[60],q[60];//v钱数，w重要度，q主件和附件编号 long long vgroup[60][3] = { 0 }, wgroup[60][3] = { 0 };//第0列是主件，第1列是第一个附件，第1列是第二个附件的属性 int index[60] = { 0 };//记录编号为i的物品附件的个数 long long maxvalue[32000] = { 0 }; int main() { int i, j; cin >> N >> m; for (i = 1; i <= m; i++) { cin >> v[i] >> w[i] >> q[i];//读入数据 if (q[i] == 0) //主件的数据移动到新的数组的第0列 { vgroup[i][0] = v[i]; wgroup[i][0] = w[i]; } if (q[i] > 0)//记录附件属性 { index[q[i]]++; vgroup[q[i]][index[q[i]]] = v[i]; wgroup[q[i]][index[q[i]]] = w[i]; } } for (i = 1; i <= m; i++) //DP for (j = N; j >= 1; j--) if (q[i] == 0) { if (vgroup[i][0] <= j) //取主件 maxvalue[j] = max(maxvalue[j - vgroup[i][0]]+vgroup[i][0]*wgroup[i][0], maxvalue[j]); if (vgroup[i][0] + vgroup[i][1] <= j)//取主件加附件1 maxvalue[j] = max(maxvalue[j - vgroup[i][0] - vgroup[i][1]] + vgroup[i][0] * wgroup[i][0] + vgroup[i][1] * wgroup[i][1], maxvalue[j]); if (vgroup[i][0] + vgroup[i][2] <= j)//取主件加附件2 maxvalue[j] = max(maxvalue[j - vgroup[i][0] - vgroup[i][2]] + vgroup[i][0] * wgroup[i][0] + vgroup[i][2] * wgroup[i][2], maxvalue[j]); if (vgroup[i][0] + vgroup[i][1] + vgroup[i][2] <= j)//全部取 maxvalue[j] = max(maxvalue[j - vgroup[i][0] - vgroup[i][1]- vgroup[i][2]] + vgroup[i][0] * wgroup[i][0] + vgroup[i][1] * wgroup[i][1] + vgroup[i][2] * wgroup[i][2], maxvalue[j]); } cout << maxvalue[N] << endl; system("pause"); return 0; } -
0
#include <iostream>
using namespace std;
int inline max(int a,int b){return (a>b? a:b);}
struct Object{
int price=0;
int val=0;
int attach_num=0; // store the number of attachment, -1 is it is a attach
Object* attach[2]={0};
};
void read(Object* object,int number,int price,int val,int attach_to){
Object* my_object=object+number;
my_object->price=price;
my_object->val=val*price;
if (attach_to!=0){
my_object->attach_num=-1;
my_object=object+attach_to-1;
(my_object->attach_num)++;
my_object->attach[my_object->attach_num-1]=object+number;
}
}
int total_val(Object* object,int type){
//type = 0, no attach
//type = 1, first attah
//type = 2, second attach
//type = 3, two attaches
switch (type){
case 0:return(object->val);break;
case 1:return(object->val+object->attach[0]->val);break;
case 2:return(object->val+object->attach[1]->val);break;
case 3:return(object->val+object->attach[1]->val+object->attach[0]->val);break;
default:return(0);break;
}
}
int total_price(Object* object,int type){
switch (type){
case 0:return(object->price);break;
case 1:return(object->price+object->attach[0]->price);break;
case 2:return(object->price+object->attach[1]->price);break;
case 3:return(object->price+object->attach[1]->price+object->attach[0]->price);break;
default:return(0);break;
}
}
void dp(int* f,int money,Object* object,int type){
int price=total_price(object,type);
if (money<price) return;
int val=total_val(object,type);
f[money]=max(f[money],f[money-price]+val);
}
int main(){
int N,m;//N -- money, m objects
cin >> N >> m;
Object* object=new Object[m];
int temp1,temp2,temp3;
for (int i = 0; i < m; i++){
cin >> temp1 >> temp2 >> temp3;
read(object,i,temp1,temp2,temp3);
}
int* f=new int[N+1];// the best budget using N money
for (int i = 0; i < m; i++){
for (int j = N;j >= 0; j--){
for (int k = 0; k <= object[i].attach_num ; k++){
dp(f,j,object+i,k);
}
if (object[i].attach_num==2) dp(f,j,object+i,3);
}
}
cout << f[N] << endl;
delete[] f;
delete[] object;
return 0;
} -
0
#include <bits/stdc++.h> using namespace std; int n, m; int cost[100]; int val[100]; vector<int> major; vector<int> minor[100]; int dp[32010]; int dp2[32010]; int main() { scanf("%d%d", &n, &m); for(int i = 0; i < m; ++i) { int v, p, q; scanf("%d%d%d", &v, &p, &q); cost[i] = v; val[i] = v * p; if(q == 0) { major.push_back(i); } else { minor[q-1].push_back(i); } } memset(dp, 0, sizeof dp); for(int i = 0; i < major.size(); ++i) { int cur = major[i]; // initialize dp2 for(int v = 0; v <= n; ++v) { if(v < cost[cur]) dp2[v] = -1; else dp2[v] = dp[v - cost[cur]] + val[cur]; } for(int j = 0; j < minor[cur].size(); ++j) { int idx = minor[cur][j]; for(int v = n; v >= cost[idx] + cost[cur]; --v) { dp2[v] = max(dp2[v], dp2[v - cost[idx]] + val[idx]); } } for(int v = 0; v <= n; ++v) { dp[v] = max(dp[v], dp2[v]); } } printf("%d\n", dp[n]); } -
0
#include<bits/stdc++.h>
using namespace std;
struct node
{
int tot;
int v[5];
int w[5];
}d[61];
long long f[32001];
int n,m;
int main()
{ memset(f,0,sizeof(f));
cin>>n>>m;
for (int i=1;i<=m;i++)
d[i].tot=0;
for (int i=1;i<=m;i++)
for (int j=0;j<=5;j++)
d[i].v[j]=10005;
for (int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
if (c==0)
d[i].v[0]=a,d[i].w[0]=b*a;
else
d[c].tot++,d[c].v[d[c].tot]=a,d[c].w[d[c].tot]=a*b;
}
for (int i=1;i<=m;i++)
for (int j=n;j>=0;j--)
{
if (j-d[i].v[0]>=0)
f[j]=max(f[j-d[i].v[0]]+d[i].w[0],f[j]);
if (j-d[i].v[1]-d[i].v[0]>=0&&d[i].tot>=1)
f[j]=max(f[j-d[i].v[0]-d[i].v[1]]+d[i].w[0]+d[i].w[1],f[j]);
if (j-d[i].v[2]-d[i].v[0]>=0&&d[i].tot>=2)
f[j]=max(f[j-d[i].v[0]-d[i].v[2]]+d[i].w[0]+d[i].w[2],f[j]);
if (j-d[i].v[1]-d[i].v[0]-d[i].v[2]>=0&&d[i].tot>=2)
f[j]=max(f[j-d[i].v[0]-d[i].v[1]-d[i].v[2]]+d[i].w[0]+d[i].w[1]+d[i].w[2],f[j]);
}
cout<<f[n]<<endl;
return 0;
} -
0
最多只有两件副的，所以傻傻的暴力下下就行，一定要注意0，1和等号
#include<iostream> #include<cmath> #include<cstring> #include<cstdio> #include<cstdlib> using namespace std; int n,m,v,p,q; int imp[108][3],vo[108][3],f[108][40000]; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { cin>>v>>p>>q; if(!q) {vo[i][0]=v; imp[i][0]=p;} else { if(!vo[q][1]) {vo[q][1]=v; imp[q][1]=p;} else {vo[q][2]=v; imp[q][2]=p;} } } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { if(j-vo[i][0]>=0) { f[i][j]=max(f[i-1][j],f[i-1][j-vo[i][0]]+vo[i][0]*imp[i][0]); if(j-vo[i][0]-vo[i][1]>=0) f[i][j]=max(f[i][j],f[i-1][j-vo[i][0]-vo[i][1]]+vo[i][0]*imp[i][0]+vo[i][1]*imp[i][1]); if(j-vo[i][0]-vo[i][2]>=0) f[i][j]=max(f[i][j],f[i-1][j-vo[i][0]-vo[i][2]]+vo[i][0]*imp[i][0]+vo[i][2]*imp[i][2]); if(j-vo[i][0]-vo[i][1]-vo[i][2]>=0) f[i][j]=max(f[i][j],f[i-1][j-vo[i][0]-vo[i][1]-vo[i][2]]+vo[i][0]*imp[i][0]+vo[i][1]*imp[i][1]+vo[i][2]*imp[i][2]); } else f[i][j]=f[i-1][j]; } cout<<f[m][n]; return 0; } -
0
树形动归
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline const void read(int &a)
{
a=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=a*10+c-'0';
c=getchar();
}
}
class article
{
public:
int v,p,left,right;//价 权
}t[61];
int n,m,d=0;
int to[1000],nex[1000],ans[61][3201];
bool cal[61][3201];
int dfs(int p,int rest)
{
if(cal[p][rest])return ans[p][rest];//防止重复计算
cal[p][rest]=true;
if(rest>=t[p].v)ans[p][rest]=t[p].v*t[p].p;//只取自己
if(t[p].left&&t[p].right)//左右儿子和自己都取
{
for(int i=0;i<=rest-t[p].v;i++)//给左儿子分担i，右儿子分担rest-i-t[p].v
ans[p][rest]=max(ans[p][rest],dfs(t[p].left,i)+dfs(t[p].right,rest-t[p].v-i)+t[p].v*t[p].p);
}
if(t[p].left)//取左儿子与自己
if(rest>=t[p].v)ans[p][rest]=max(ans[p][rest],dfs(t[p].left,rest-t[p].v)+t[p].v*t[p].p);
if(t[p].right)//取右儿子与自己或只取右儿子
{
ans[p][rest]=max(ans[p][rest],dfs(t[p].right,rest));
if(rest>=t[p].v)ans[p][rest]=max(ans[p][rest],dfs(t[p].right,rest-t[p].v)+t[p].v*t[p].p);
}
return ans[p][rest];
}
int main()
{
//freopen("测试数据.txt","r",stdin);
memset(nex,0,sizeof(nex));
memset(ans,0,sizeof(ans));
memset(cal,false,sizeof(cal));
read(n);read(m);
n/=10;
for(int i=0;i<=m;i++)t[i].v=t[i].left=t[i].right=0;
for(int i=1;i<=m;i++)
{
int k;
read(t[i].v);read(t[i].p);read(k);
t[i].v/=10;d++;
if(t[k].left)
{
k=t[k].left;
while(t[k].right)k=t[k].right;
t[k].right=i;
}
else t[k].left=i;
}
printf("%d",dfs(0,n)*10);
return 0;
} -
0
#1 Accepted 1ms 200.0KiB
#2 Accepted 1ms 200.0KiB
#3 Accepted 1ms 208.0KiB
#4 Accepted 1ms 256.0KiB
#5 Accepted 2ms 204.0KiB
#6 Accepted 2ms 204.0KiB
#7 Accepted 2ms 256.0KiB
#8 Accepted 3ms 196.0KiB
#9 Accepted 5ms 200.0KiB
#10 Accepted 1ms 256.0KiB
很简单的思路。var w, v:array[1..60, 1..3] of longint; fu:array[1..60, 1..3] of longint; f:array[0..3200] of longint; p:array[1..60] of longint; n, x, k, m, fm, tw, tv, i, j:longint; begin readln(x, n); x:=x div 10; fillchar(w, sizeof(w), 0); fillchar(v, sizeof(v), 0); fillchar(fu, sizeof(fu), 0); fillchar(p, sizeof(p), 0); m:=0; fm:=0; for i:=1 to n do begin readln(tw, tv, k); if k=0 then begin inc(m); w[m, 1]:=tw div 10; v[m, 1]:=tw*tv div 10; p[m]:=i end else begin inc(fm); fu[fm, 1]:=tw div 10; fu[fm, 2]:=tw*tv div 10; fu[fm, 3]:=k end; end; for i:=1 to fm do for j:=1 to m do if p[j]=fu[i, 3] then if w[j, 2]=0 then begin w[j, 2]:=fu[i, 1]; v[j, 2]:=fu[i, 2]; break end else begin w[j, 3]:=fu[i, 1]; v[j, 3]:=fu[i, 2]; break end; fillchar(f, sizeof(f), 0); for i:=1 to m do for j:=x downto w[i, 1] do begin if f[j-w[i, 1]]+v[i, 1]>f[j] then f[j]:=f[j-w[i, 1]]+v[i, 1]; if (j-w[i, 1]-w[i, 2]>-1) and (f[j-w[i, 1]-w[i, 2]]+v[i, 1]+v[i, 2]>f[j]) then f[j]:=f[j-w[i, 1]-w[i, 2]]+v[i, 1]+v[i, 2]; if (j-w[i, 1]-w[i, 3]>-1) and (f[j-w[i, 1]-w[i, 3]]+v[i, 1]+v[i, 3]>f[j]) then f[j]:=f[j-w[i, 1]-w[i, 3]]+v[i, 1]+v[i, 3]; if (j-w[i, 1]-w[i, 2]-w[i, 3]>-1) and (f[j-w[i, 1]-w[i, 2]-w[i, 3]]+v[i, 1]+v[i, 2]+v[i, 3]>f[j]) then f[j]:=f[j-w[i, 1]-w[i, 2]-w[i, 3]]+v[i, 1]+v[i, 2]+v[i, 3] end; write(f[x]*10) end.先读入，在一点点处理。因为价格和价值都是10的整倍数，因此可以先除10，最后再乘10。
-
0
Sky1231 (sky1231) LV 10 @ 2017-01-19 22:09:04
//好不爽,被编号坑了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int f[61][32001],cn[61],cx[61],n,m,g=0;
struct node1
{
int v,p,q;
}a[61];struct node2
{
int v,p;
}c[61][5];int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
a[i].p*=a[i].v;
}
memset(cn,0,sizeof(cn));
for (int i=1;i<=m;i++)
{
if (a[i].q==0)
{
g++;
cx[i]=g;
cn[g]++;
c[g][cn[g]].p=a[i].p;
c[g][cn[g]].v=a[i].v;
}
else
{
int x=cx[a[i].q];
cn[x]++;
c[x][cn[x]].p=c[x][1].p+a[i].p;
c[x][cn[x]].v=c[x][1].v+a[i].v;
if (cn[x]==3)
{
cn[x]++;
c[x][cn[x]].p=c[x][2].p+c[x][3].p-c[x][1].p;
c[x][cn[x]].v=c[x][2].v+c[x][3].v-c[x][1].v;
}
}
}
memset(f,0,sizeof(f));
for (int i=1;i<=g;i++)
for (int j=n;j>=0;j--)
for (int k=1;k<=cn[i];k++)
{
f[i][j]=max(f[i][j],f[i-1][j]);
if (j>=c[i][k].v)
f[i][j]=max(f[i][j],f[i-1][j-c[i][k].v]+c[i][k].p);
}
printf("%d\n",f[g][n]);
} -
0
#include <iostream>
#include <vector>
#include <map>using namespace std;
#define MAXM 32001
#define MAXN 61int m,n;
int f[MAXM],w[MAXN],c[MAXN],o[MAXN];
map < int,vector <int> >p;int main()
{
int i,j;
cin>>m>>n;
for(i=1;i<=n;++i)
{
cin>>w[i]>>c[i]>>o[i];
if(o[i]!=0)p[o[i]].push_back(i);
}
for(i=1;i<=n;++i)
{
if(o[i])continue;
for(j=m;j>=w[i];--j)
{
int a=w[i]*c[i],b=j-w[i];
switch(p[i].size())
{
case 2:
if(b-w[p[i][0]]-w[p[i][1]]>=0)
f[j]=max(f[j],f[b-w[p[i][0]]-w[p[i][1]]]+a+w[p[i][0]]*c[p[i][0]]+w[p[i][1]]*c[p[i][1]]);
if(b-w[p[i][1]]>=1)
f[j]=max(f[j],f[b-w[p[i][1]]]+a+w[p[i][1]]*c[p[i][1]]);
case 1:
if(b-w[p[i][0]]>=0)
f[j]=max(f[j],f[b-w[p[i][0]]]+a+w[p[i][0]]*c[p[i][0]]);
case 0:
f[j]=max(f[j],f[b]+a);
}
}
}
cout<<f[m];
return 0;
} -
0
Accepted_upc LV 8 @ 2016-09-10 09:15:09
垃圾……
#include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #define maxn (1000 + 20) #define inf 0x3f3f3f3f #define pi acos(-1.0) using namespace std; typedef long long int LLI; struct node { int v; int p; int q; int vp; node() { v = -1; } }; node zhujian[maxn],fujian1[maxn],fujian2[maxn]; vector<node> ans[maxn]; int dp[32000 + 50]; int main() { // freopen("in.txt","r",stdin); // freopen("out1.txt","w",stdout); int n,m; scanf("%d%d",&n,&m); for(int i = 1; i <= m; i ++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(z == 0) { zhujian[i].v = x; zhujian[i].p = y; zhujian[i].q = i; zhujian[i].vp = x * y; } else { if(fujian1[z].v == -1) { fujian1[z].v = x; fujian1[z].p = y; fujian1[z].vp = x * y; } else { fujian2[z].v = x; fujian2[z].p = y; fujian2[z].vp = x * y; } } } int cnt = m; for(int i = 1; i <= m; i ++) { if(zhujian[i].v == -1) continue; if(fujian1[i].v != -1) { zhujian[++cnt].vp = fujian1[i].vp + zhujian[i].vp; zhujian[cnt].v = fujian1[i].v + zhujian[i].v; zhujian[cnt].q = i; } if(fujian2[i].v != -1) { zhujian[++cnt].v = fujian2[i].v + zhujian[i].v; zhujian[cnt].vp = fujian2[i].vp + zhujian[i].vp; zhujian[cnt].q = i; zhujian[++cnt].v = fujian2[i].v + zhujian[i].v + fujian1[i].v; zhujian[cnt].vp = fujian2[i].vp + zhujian[i].vp + fujian1[i].vp; zhujian[cnt].q = i; } } for(int i = 1; i <= cnt; i ++) { if(zhujian[i].v == -1) continue; int k = zhujian[i].q; ans[k].push_back(zhujian[i]); // printf("%d %d %d\n",zhujian[i].v,zhujian[i].vp,zhujian[i].q); } for(int i = 0; i < 60; i ++) { if(ans[i].size() == 0) continue; for(int j = n; j >= 0; j --) { for(int k = 0; k < ans[i].size(); k ++) { if(j < ans[i][k].v) continue; dp[j] = max(dp[j],dp[j - ans[i][k].v] + ans[i][k].vp); } } } // for(int i = 0; i <= 60; i ++) { // if(ans[i].size() == 0) continue; // for(int k = 0; k < ans[i].size(); k ++) { // printf("%d %d %d\n",ans[i][k].v,ans[i][k].p,ans[i][k].q); // } // printf("\n"); // } printf("%d\n",dp[n]); return 0; } -
0
因为最多2个附属 用捆绑法 共3种情况
不能开始时将主附捆绑作为新的一个去枚举,这样会有重复，需枚举主见即可
uses math;
type re=record
a,b:longint;
end;
var
i,j,k,m,n,j1:longint;
a,b,d:array[0..200]of longint;
c:array[0..200]of re;
f:array[0..35000]of longint;
begin
readln(n,m);
fillchar(c,sizeof(c),0);
j1:=0;
for i:=1 to m do
begin
read(a[i]);
read(j);
read(k);
d[i]:=k;
b[i]:=a[i]*j;
if k>0 then
if c[k].a<>0 then
c[k].b:=i else c[k].a:=i;
end;
for i:=1 to m do
for j:=n downto a[i] do
if d[i]=0 then
begin
f[j]:=max(f[j],f[j-a[i]]+b[i]);
if (c[i].a<>0) and (c[i].b<>0) and (j-a[i]-a[c[i].a]-a[c[i].b]>=0) then
f[j]:=max(f[j],f[j-a[i]-a[c[i].a]-a[c[i].b]]+b[i]+b[c[i].a]+b[c[i].b]);
if (c[i].a<>0) and (j-a[i]-a[c[i].a]>=0) then
f[j]:=max(f[j],f[j-a[i]-a[c[i].a]]+b[i]+b[c[i].a]);
if (c[i].b<>0) and (j-a[i]-a[c[i].b]>=0) then
f[j]:=max(f[j],f[j-a[i]-a[c[i].b]]+b[i]+b[c[i].b]);
end;
writeln(f[n]);
end. -
0
DP
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 50000 + 5;
const int INF = 1000000000;
struct Node{
int v, w;
};
int n, m, d[maxn];vector<Node> vec[maxn];
void init(){
int tot = 0, x, y, z;cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> x >> y >> z;
if(z) vec[z].push_back((Node){x, y});
else vec[i].push_back((Node){x, y});
}
for(int i = 0; i <= n; i++)
d[i] = 0;}
void work(){
for(int i = 1; i <= m; i++){
if(vec[i].empty()) continue;
for(int j = n; j >= 0; j--){
if(j >= vec[i][0].v){
//只买主件
d[j] = max(d[j], d[j-vec[i][0].v] + vec[i][0].w * vec[i][0].v);
//只买某一个附件
for(int k = 1; k < vec[i].size(); k++){
if(j >= vec[i][0].v + vec[i][k].v)
d[j] = max(d[j], d[j-vec[i][0].v-vec[i][k].v] + vec[i][k].w * vec[i][k].v + vec[i][0].w * vec[i][0].v);
//两个附件一起
if(vec[i].size() > 2 && j >= vec[i][0].v + vec[i][1].v + vec[i][2].v)
d[j] = max(d[j], d[j-vec[i][0].v-vec[i][1].v-vec[i][2].v] + vec[i][1].w * vec[i][1].v + vec[i][2].w * vec[i][2].v + vec[i][0].w * vec[i][0].v);}
}
}
}
}
int main(){
init();
work();
cout << d[n];
return 0;
}
```
浮光过客
LV 10
@ 2015-10-08 19:58:44
