題意：存錢罐可以往里面放一些價(jià)值小的錢，但是時(shí)間久了就不知道里面有多少錢了，除非你打破它。現(xiàn)在給出空罐子的重量和最滿能裝到多重，然后給出每種硬幣的價(jià)值和重量，我們要在不打破它的情況下確認(rèn)罐子里最少有多少錢。 for i 1~n; for j w[i]~weight； dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); 由于 http://blog.csdn.net/tbwood/article/details/22747215 這個(gè)大牛說(shuō)過(guò)。當(dāng)前狀態(tài)至于上一個(gè)狀態(tài)的當(dāng)前位置和上一個(gè)狀態(tài)的前一個(gè)位置有關(guān)，可以用一維數(shù)組。 dp[i]=max(dp[j],dp[j-w[i]]+v[i]);
#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace std;const int maxn = 10010;const int inf = 0x3f3f3f3f;int c[maxn];int v[maxn];int dp[maxn];int main(){ int T; cin>>T; while(T--) { int E,F; cin>>E>>F; int n; cin>>n; for(int i=1;i<=F-E;i++) dp[i]=inf; for(int i=1;i<=n;i++) cin>>c[i]>>v[i]; for(int i=1;i<=n;i++) { for(int j=v[i];j<=F-E;j++) { dp[j]=min(dp[j-v[i]]+c[i],dp[j]); } } if(dp[F-E]>=inf) cout<<"This is impossible."<<endl; else {新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
