《背包问题》大佬们帮帮蒟蒻啊!

回复帖子

@tan_gent 2018-02-20 14:01 回复

这种方法为什么不行?

我优先拿了价值除以重量的值最大的物品。

代码如下:

include 《cstdio>

include 《iostream>

using namespace std;

int n,m,c[888],w[888],h[888],sum,msum,hehe;

int main() {

cin>>n>>m;
for(int i=1; i<=n; i++) {
    cin>>c[i]>>w[i];
}
for(int i=1; i<=n; i++) {
    h[i]=w[i]/c[i];
}
for(int j=1; j<=n; j++) {
    for(int i=1; i<=n; i++) {
        if(h[i]<h[i+1]) {
            hehe=h[i];
            h[i]=h[i+1];
            h[i+1]=hehe;
            hehe=c[i];
            c[i]=c[i+1];
            c[i+1]=hehe;
            hehe=w[i];
            w[i]=w[i+1];
            w[i+1]=hehe;
        }
    }
}
for(int i=1; i<=n; i++) {
    if(msum>m) {
        sum-=w[i-1];
        break;
    } else {
        msum+=c[i];
        sum+=w[i];
    }
}
cout<<sum;
return 0;

}

@deco  2018-02-20 14:43 回复 举报

@蒟蒻chi_chi 至于你这个方法的问题,你可以想个例子,比如说我有三个物品,重量分别是6 4 5,价值分别是 12 7 9,背包空间为9,按你的方法优先选择了一号物品就装不下了,而选择二号和三号明显优于只选一号,你的方法问题就出在这

@yy233 2018-03-17 18:15 回复 举报

同志,对于这种题目应该用一种叫做动态规划的算法而不是这种叫做贪心的算法。 上AC代码

include<bits/stdc++.h>

using namespace std; int v,n,w[3403],c[3403],opt[12881]; int main() { cin>>n>>v; for(int i=1;i<=n;i++) cin>>w[i]>>c[i]; for(int i=1;i<=n;i++) for(int j=v;j>=w[i];j--) opt[j]=max(opt[j-1],opt[j-w[i]]+c[i]); cout<<opt[v]<<endl; return 0; }//其实我也不知道发生了什么

@yy233 2018-04-29 14:41 回复 举报

@rgq233666 ```cpp

include<bits/stdc++.h>

using namespace std; int v,n,w[3403],c[3403],opt[12881]; int main() { cin>>n>>v; for(int i=1;i<=n;i++) cin>>w[i]>>c[i]; for(int i=1;i<=n;i++) for(int j=v;j>=w[i];j--) opt[j]=max(opt[j-1],opt[j-w[i]]+c[i]); cout<<opt[v]<<endl; return 0; }

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。