ltdj @ 2019-05-23 12:19:37
#include <iostream>
#include <string.h>
using namespace std;
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,m;
int v[80],w[80],p[80],f[2][30000];
memset(f,0,sizeof(f));
memset(p,0,sizeof(p));
cin >> m >> n;
for(int i=1;i<=n;i++)
cin >> v[i] >> w[i] >> p[i];
for(int i=1;i<=n;i++){
if(p[i]!=0){
int l=0,t=i;
for(int c=1;c<=n;c++){
if(p[c]==0) l++;
if(l==p[i]){
l=c;
break;
}
}
int pt=p[t],vt=v[t],wt=w[t];
if(t>=l){
for(int j=t-1;j>=l+1;j--){
p[j+1]=p[j];
v[j+1]=v[j];
w[j+1]=w[j];
}
p[l+1]=pt;
v[l+1]=vt;
w[l+1]=wt;
}else{
for(int j=t+1;j<=l;j++){
p[j-1]=p[j];
v[j-1]=v[j];
w[j-1]=w[j];
}
p[l]=pt;
v[l]=vt;
w[l]=wt;
}
}
}
for(int i=1;i<=n;i++){
//cout << v[i] << '\t' << w[i]<<'\t'<< p[i]<<'\n';
}
int h=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
f[i%2][j]=f[(i-1)%2][j];
int l=f[(i-1)%2][j];
if(j<v[h]) continue;
f[i%2][j]=f[(i-1)%2][j-v[h]] + v[h]*w[h];
if(p[h+1]!=0 && j>=(v[h]+v[h+1]))
f[i%2][j]=max(f[i%2][j] , f[(i-1)%2][j-v[h]-v[h+1]] + v[h]*w[h] + v[h+1]*w[h+1]);
if(p[h+2]!=0 && j>=(v[h]+v[h+2]))
f[i%2][j]=max(f[i%2][j] , f[(i-1)%2][j-v[h]-v[h+2]] + v[h]*w[h] + v[h+2]*w[h+2]);
if(p[h+2]!=0 && p[h+1]!=0 && j>=(v[h]+v[h+1]+v[h+2]))
f[i%2][j]=max(f[i%2][j] , f[(i-1)%2][j-v[h]-v[h+1]-v[h+2]] + v[h]*w[h] + v[h+1]*w[h+1] +v[h+2]*w[h+2]);
f[i%2][j]=max(f[i%2][j] , l);
}
h++;
while(p[h]!=0 && h<=n) h++;
if(h>n){
cout << f[i%2][m];
return 0;
}
}
return 0;
}万分感谢
by 忘无羡机 @ 2019-05-23 13:08:16
一道背包给你写成这样也是可怕
by 忘无羡机 @ 2019-05-23 13:11:00
首先你得会一点基本的背包，代码里注释很详细了，拿去不谢
#include<bits/stdc++.h>
using namespace std;
int n,m,v1,p1,q1,w[100],v[100],fw[100][3],fv[100][3],f[33333],fnum[10000];
int max(int a,int b){return(a > b ? a : b);}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&v1,&p1,&q1);
if(!q1) //如果是主件
{
v[i] = v1; //储存一下主件体积
w[i] = v1 * p1; //计算一下主件价值
}
else
{
fnum[q1]++; //记录主件q1对应的数量
fv[q1][fnum[q1]]=v1; //分别记录q1内编号为fnum[q1]的体积
fw[q1][fnum[q1]]=v1*p1; //分别记录q1内编号为fnum[q1]的价值
}
}
for(int i=1; i<=m; i++) //枚举一下所有物品
for(int j=n; j>=v[i]; j--) //再接着枚举总体积
{
f[j]=max(f[j],f[j-v[i]]+w[i]); //将主件放入背包
if(j>=v[i]+fv[i][1]) //判断放入主件后，附件1还可不可以放入
f[j]=max(f[j],f[j-v[i]-fv[i][1]]+w[i]+fw[i][1]);
if(j>=v[i]+fv[i][2]) //判断放入主件后，附件2还可不可以放入
f[j]=max(f[j],f[j-v[i]-fv[i][2]]+w[i]+fw[i][2]);
if(j>=v[i]+fv[i][1]+fv[i][2]) //判断放入主件后，附件1和2还可不可以同时放入
f[j]=max(f[j],f[j-v[i]-fv[i][1]-fv[i][2]]+w[i]+fw[i][1]+fw[i][2]);
}
printf("%d",f[n]);
}by 忘无羡机 @ 2019-05-23 13:12:06
动归还是要好好学的（来自退役多年的人的感慨）
by ferrum_cccp @ 2019-05-23 13:35:21
动归还是很好学的