给定n个物品的重量和两艘载重量分别为c1和c2的船,问能否用这两艘船装下所有的物品。
刚开始还以为可以搞贪心,脑子短路了,后来想想,都使劲往一个背包塞可以搞成01背包问题。。ok
具体的要先往哪个背包塞还有待考量......
程序代码如下:
#include#include #define max(a,b) a>b?a:bconst int NMAX=103;const int MAX=5003;int value[NMAX],volumn[NMAX];int dp[MAX];int main(){ int n,i,j,c1,c2; while(~scanf("%d%d%d",&n,&c1,&c2)) { int sum=0; for(i=1;i<=n;i++){ scanf("%d",value+i); volumn[i]=value[i]; sum+=value[i]; } memset(dp,0,sizeof(dp)); //一维01背包实现 for(i=1;i<=n;i++) { for(j=c1;j>=volumn[i];j--) dp[j]=max(dp[j],dp[j-volumn[i]]+value[i]); } if(sum-dp[c1]>c2) puts("NO"); else puts("YES"); } return 0;}