問題 J: 【動態規劃】簡單背包問題II
時間限制: 1 Sec??內存限制: 64 MB
提交: 127??解決: 76
[提交] [狀態] [討論版] [命題人:admin]
?
題目描述
張琪曼：“為什么背包一定要完全裝滿呢？盡可能多裝不就行了嗎？”
李旭琳：“你說得對，這和墨老師曾告訴我們的‘日中則昃，月滿則虧’是一個道理。”所以，現在的問題是，她們有一個背包容量為v(正整數，０≤v≤20000)，同時有n個魔法石(０≤n≤30)，每個魔法石有一個體積 (正整數)。要求從n個魔法石中，任取若干個裝入包內，使背包的剩余空間為最小。
?
輸入
第一行為一個整數，表示背包容量，第二行為一個整數，表示有n個魔法石，接下來n行，分別表示這n個魔法石的各自體積。
?
輸出
只有一個整數，表示背包剩余空間。
?
樣例輸入
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;}| ? |
)
