題目連結
算法：動态規劃（01背包）
01背包思想：依次對待某一物體，考慮是否放入容量為V的背包中
用f[V]來表示容量為V的背包的最大價值，則決策是
f[V] = max{f[V], f[V-v[i]]+w[i]} （0 <= i <= n， V-v[i] >= 0）
解釋：每一個物體i，隻有兩種選擇，是否放入（放入後一定體積要等于容量V）容量為V的背包中，如果放入的話，那麼就要比較現在容量為V的背包不放入i物體 與放入i物體到容量為V-v[i]的背包（價值即為f[V-v[i]]+w[i]）哪個大，比f[V]大的話，那麼就放入此物體i到容量為V的背包中
（自己慢慢體會，看白書有講）
注意：此題隻需将w看成是物品i的價值，算出最大價值再用v減去就是答案
設狀态f[v]表示v容量的背包的最大價值，則
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 35, V = 20005;
int f[V], w, v, j;
int main()
{
cin >> v >> w; //不需要讀入n，，對于下面那句來說沒有必要
//滾動數組 w既表示體積，又表示價值
while(cin >> w)
for(j = v; j >= w; j--) //依次判斷是否将物體放入容量為j的背包中
f[j] = max(f[j], f[j-w]+w);
cout << v - f[v];
return 0;
} 部落格位址：www.cnblogs.com/iwtwiioi 本文為部落客原創文章，未經部落客允許不得轉載。一經發現，必将追究法律責任。