栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 1293 Duty Free Shop

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 1293 Duty Free Shop

#include <iostream>using namespace std;int M,L,c[1010],dp[1010],n,pre[1010],sum,ans;bool v[1010];void dfs(int j) {     if (j==0) return;     v[pre[j]] = 0;     dfs(j-c[pre[j]]);}int main() {    while (scanf("%d%d",&M,&L)) {          if (M==0 && L==0) break;          scanf("%d",&n);          for (int i=1;i<=n;i++) {   scanf("%d",&c[i]);   v[i] = 1;          }          memset(dp,0,sizeof(dp));          for (int i=1;i<=n;i++)   for (int j=M;j>=c[i];j--)       if (dp[j]<dp[j-c[i]]+c[i]) {          dp[j] = dp[j-c[i]]+c[i];          pre[j] = i;       }          dfs(dp[M]);          sum = 0;          ans = n;          for (int i=1;i<=n;i++)   if (v[i]==1) {     sum += c[i];     ans--;   }          if (sum<=L) {printf("%d",ans);for (int i=1;i<=n;i++)    if (v[i]==0) printf(" %d",i);printf("n");          }          else printf("Impossible to distributen");    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/380166.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号