問題 J: 【動態(tài)規(guī)劃】簡單背包問題II

時間限制: 1 Sec??內(nèi)存限制: 64 MB
提交: 127??解決: 76
[提交] [狀態(tài)] [討論版] [命題人:admin]

?

題目描述

張琪曼：“為什么背包一定要完全裝滿呢？盡可能多裝不就行了嗎？”

李旭琳：“你說得對，這和墨老師曾告訴我們的‘日中則昃，月滿則虧’是一個道理?！彼?#xff0c;現(xiàn)在的問題是，她們有一個背包容量為v(正整數(shù)，０≤v≤20000)，同時有n個魔法石(０≤n≤30)，每個魔法石有一個體積 (正整數(shù))。要求從n個魔法石中，任取若干個裝入包內(nèi)，使背包的剩余空間為最小。

?

輸入

第一行為一個整數(shù)，表示背包容量，第二行為一個整數(shù)，表示有n個魔法石，接下來n行，分別表示這n個魔法石的各自體積。

?

輸出

只有一個整數(shù)，表示背包剩余空間。

?

樣例輸入

24 6 8 3 12 7 9 7

?

樣例輸出

0

?

AC代碼

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace std;int n,v;int w[100100];int f[100100];int zeroone(){for(int i=1;i<=n;i++)for(int j=v;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+w[i]);return f[v];}int main(){cin>>v>>n;for(int i=1;i<=n;i++)cin>>w[i];cout<<v-zeroone()<<endl;return 0;}

?

總結

以上是生活随笔為你收集整理的【动态规划】简单背包问题II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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