[Algorithm Elementary]简单的背包dp

Thinking Process

1、先确定状态

f[i][j]:前i个物体能不能装满体积为j的背包?
则现在有两个选择：

1. 选第i个物体：要看一下f[i-1][j-c[i]]，它能装下，那这个决定就可以装下
2. 不选第i个物体：要看一下f[i-1][j]
   故推出状态方程：

f[i][j] = f[i - 1][j] || f[i - 1][j - c[i]]

2、就地滚动

f[i][j]的状态都只依赖于上一行，故我们可以压缩数组的空间大小，将二维的变成一维的。

for(int i = 1;i <= n ; i ++ ) {
	for(int j = v; j >= c[i];j -- ){
    	···
    } 
} 

Code

#include<iostream>
using namespace std;

int v, n;
int a[40];
int dp[20100];

int main() {
    cin >> v >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    dp[0] = 1;
    for(int i = 1;i <= n; i ++ ) {
        for(int j = v; j >= a[i]; j --) {
            dp[j] = dp[j] || dp[j - a[i]];
        }
    }
    for(int j = v;j >= 0;j --) {
        if(dp[j]) {
            cout << v - j;
            break;
        } 
    } 
}