??這題解法中用到了一個(gè)物品組的概念，跟背包九講的提到的差不多，當(dāng)我們不討論當(dāng)前擁有哪些物品，而只看我們當(dāng)前的價(jià)值和的時(shí)候，就會(huì)變成一個(gè)01背包后很簡(jiǎn)單的貪心題。。

　這題中交換物品的時(shí)候是只要交換前后物品價(jià)值和不超過(guò)d就是可行的。所以當(dāng)我們使用物品組的概念的時(shí)候能夠忽略掉具體交換的細(xì)節(jié)，變成對(duì)總價(jià)值的貪心。。

　　

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=2e6; 4 int a[maxn],dp[maxn]; 5 int main() 6 { 7 int n,d; 8 scanf("%d%d",&n,&d); 9 for(int i=1;i<=n;i++) 10 scanf("%d",&a[i]); 11 dp[0]=1; 12 for(int i=1;i<=n;i++) 13 for(int j=600000;j>=a[i];j--) 14 dp[j]=max(dp[j],dp[j-a[i]]); 15 int ans=0,num=0; 16 while(1) 17 { 18 int flag=0; 19 for(int i=ans+d;i>ans;i--) 20 if(dp[i]) 21 { 22 ans=i; 23 num++; 24 flag=1; 25 } 26 if(!flag) 27 break; 28 } 29 printf("%d %d",ans,num); 30 return 0; 31 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/julyc/p/6498218.html

總結(jié)

以上是生活随笔為你收集整理的codeforce#365D Free Market的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。