非二进制优化算法,对比两个运行时间 差距一下体现出来了
第一个是非二进制优化算法,第二个是二进制优化算法
#include<bits/stdc++.h>
using namespace std;
int dp[20005];
struct Node{
int v,w,s;
bool operator<(const Node b)const{
return (double)w/v>(double)b.w/b.v;
}
}node[1005];
int main()
{
int n,m,mx=0;
cin >> n >> m;
for(int i=0;i<n;++i){
cin >> node[i].v >> node[i].w >> node[i].s;
}
sort(node,node+n);
for(int i=0;i<n;++i){
int user[20005]={0};
for(int j=node[i].v;j<=m;++j){
if(dp[j]<dp[j-node[i].v]+node[i].w && user[j-node[i].v]+1<=node[i].s){
user[j]=user[j-node[i].v]+1;
dp[j]=dp[j-node[i].v]+node[i].w;
mx=max(mx,dp[j]);
}
}
}
cout << mx << endl;
return 0;
}
下面的是改过后的代码
`
#include<bits/stdc++.h>
using namespace std;
int dp[3][20005];
struct Node{
int v,w,s;
bool operator<(const Node b)const{
return (double)w/v>(double)b.w/b.v;
}
}node[1005];
int main()
{
int n,m,mx=0;
cin >> n >> m;
for(int i=1;i<=n;++i){
cin >> node[i].v >> node[i].w >> node[i].s;
}
sort(node+1,node+n+1);
for(int i=1;i<=n;++i){
int user[20005]={0};
memcpy(dp[i%2],dp[(i-1)%2],sizeof(int)*m);
for(int j=node[i].v;j<=m;++j){
if(dp[(i-1)%2][j-node[i].v]+node[i].w>=dp[i%2][j-node[i].v] && user[j-node[i].v]>=node[i].s && dp[(i-1)%2][j-node[i].v]+node[i].w>=dp[i%2][j]){
user[j]=1;
dp[i%2][j]=dp[(i-1)%2][j-node[i].v]+node[i].w;
}
else{
if(user[j-node[i].v]+1<=node[i].s && dp[i%2][j]<dp[i%2][j-node[i].v]+node[i].w){
dp[i%2][j]=dp[i%2][j-node[i].v]+node[i].w;
user[j]=user[j-node[i].v]+1;
}
}
mx=max(mx,dp[i%2][j]);
}
}
cout << mx << endl;
return 0;
}
对比了二进制的快了一倍,对比单调队列就快了一点,而且改后的代码看着超麻烦
`
请问20005从哪里得出来的?
厉害
厉害。还有下面写case的大哥,更牛逼。随手给个bad case
你这份代码,思路挺好,但是没有完善好。先给你组数据,你试着修复完善一下。
1 6
2 5 1
继续完善一下吧,加油↖(^ω^)↗
谢谢,这个样例运行结果不是5吗,结果是对的呀。
1 5
2 4 1 是错的,
现在已经完善了,加了一个mx
哦,一不小心数据出错了,尴尬。
厉害呀
出错的原因,因为只有一个物品还只有一件(2*1<5)所以达不到背包容量5,而我直接按最大容量输出,所以错了,哈哈 谢谢帮忙纠错。
你再试试这一组数据 :P
20 60
22 46 53
47 17 77
16 8 34
34 67 74
11 83 1
77 57 22
8 11 76
64 46 30
61 29 66
88 92 83
57 21 80
50 72 59
53 35 93
76 12 11
14 87 100
67 33 20
56 94 1
13 56 79
87 25 54
3 8 1
改了一下,感觉瞬间超级麻烦,您才是真厉害,找数据找这么厉害。佩服。之前的代码对于90%的数据都能通过,您是真的厉害,我觉得新改的代码还是有问题,真心向您请教了。
这次的暂时我还没发现什么问题。
能有不同的思路本身就很厉害了,讨论交流下还能加深对这个东西的理解。
互相探讨互相学习。
:D
这些bad case是对拍发现的吗?
前一个 case不是,因为很明显那样写有问题。
后面这个大一点儿的是对拍了下,上面重新修改的代码有没有问题,就需要其他同学来验证了。
因为,后面的我没细看(逃